Binary Search in Data Structure

 

Binary Search in Data Structure

There are various ways to search a particular element from a given list. One of them is Binary search.
When there exists so much data everywhere, it is very necessary to have a good searching method to search for the particular data in lesser time.

Binary search works faster than linear search. It is one of the fastest searching algorithms.

What is Binary Search?

It is a searching technique. It is based upon Divide and conquer strategy. Binary search is applicable only on sorted data. It takes O(log n) time for completion.

It divides the given array into halves and then checks the middle element. If the middle element is smaller than the element to be searched, the algorithm selects the second half of the array and discards the first half.

Thus, at every step, the binary search algorithm keeps on discarding half of the array based on the value of the middle element. This process continues until the array becomes of the size 1 or 2 and the algorithm finally gets the required element.

If the search is successful i.e. the element is present in the array, it returns the index of that element. If the element is not present inside the array, the algorithm returns -1.

Working of Binary Search

Suppose we wish to search 38 in the array.

Step 1: Find the middle element of the array.

index(Middle) = index(low) + index(high – low)/2.

Here, middle = 0 + (9-0)/2 = 4 i.e. the element at the 4th index i.e. 25.

Step 2: Compare 38 with the middle element. 38 > 25 So, discard the first half.

Step 3: Select the send half of the array. For the second half, low = middle+1 as shown:

Step 4: Find the middle element of this smaller array which comes out to 32. Compare 38 with 32.

38 > 32 Thus, discard the first half of this array.

Step 5: Select the remaining half of the array by doing low = middle+1 as shown:

Finally, we have found 38 and thus the algorithm will halt here.

Output:  8.