Binary Search and Jump Search

-

 2.Binary Search:

Search a list by repeatedly dividing the search interval in half. Start with a interval that covers the entire list. If the search key value is less than the mid item, reduce the interval to the lower part. Otherwise reduce it to the upper part. Check again until the value is found or the interval is empty.


Binary search algorithm :- 

STEP 1:- Compare x with the middle item.

STEP 2:- If x is the same as the middle object, we return the middle index.

STEP 3:-  Alternatively if the x is larger than the center object, then x can only lie in the sub array of the right half after the middle object. So we multiply the right half.

STEP 4:- In some cases (x less) it goes back to the left side


 

 

Time Complexity:-  O(log n)


3.Jump search:- 

Like Binary Search, Jump Search is a search algorithm for sorted arrays. The basic idea is to look for a element by skipping a fixed number of elements rather than traversing through all the elements.


Algorithm of jump search :-


Let us consider the following list: (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610). The length is 16. Jump search will find a value of 55 in the following steps assuming that the block size will be skipped or jumped by 4.

STEP 1: Jump from point 0 to point 4;

STEP 2: Jump from boat 4 to boat 8;

STEP 3: Jump from boat 8 to boat 12;

STEP 4: Since the item in index 12 is greater than 55 we will come to index 8.

STEP 5: Perform direct search from index 8 to find item 55.

 



Time Complexity:- O(√ n)


Comments

Post a Comment

Popular posts from this blog

Interpolation Search and Exponential Search

-
Image
3. Interpolation Search:- The Interpolation Search is an improvement over Binary Search for instances, where the values in a sorted array are uniformly distributed. Binary Search always goes to the middle element to check. On the other hand, interpolation search may go to different locations according to the value of the key being searched. For example, if the value of the key is closer to the last element, interpolation search is likely to start search toward the end side. To find the position to be searched, it uses following formula.  pos = lo + [ (x-arr[lo])*(hi-lo) / (arr[hi]-arr[Lo]) ]   Algorithm    Step1: In a loop, calculate the value of “pos” using the probe position formula. Step2: If it is a match, return the index of the item, and exit.  Step3: If the item is less than arr[pos], calculate the probe position of the left sub-array. Otherwise calculate the same in the right sub-array.  Step4: Repeat until a match is found o...
Read more

Introduction

-
Image
  Searching Algorithms The searching algorithms are used to search or find one or more than one element from a dataset. These type of algorithms are used to find elements from a specific data structures. Searching may be sequential or not. If the data in the dataset are random, then we need to use sequential searching. Search algorithms are designed to retrieve something or retrieve an object from any data structure in which it is stored. Depending on the type of search function, these algorithms are usually divided into two categories:-   Sequential Search : In this case, the list of elements are traverse by sequence to find a value and if the desire value is present, it will show.    Interval Search : These algorithm are used for searching in sorted data structures. This type of search algorithms works much better than Linear Search as they often point to the center of the search structure and divide the search space in half. 1.  Linear ...
Read more