Binary search

Binary search is a fast algorithm for finding an element in a sorted array. The algorithm runs in logarithmic time, making $O(\log n)$ comparisons, where $n$ is the length of the input array.

The algorithm begins by comparing the middle array element with the target value. If there is a match, it returns the element index. Otherwise, the search proceeds to the left or right subarray, depending on whether the target value is lesser or greater than the middle element. It goes on until it finds the target value or a new search interval is empty .

Example

Suppose we have an integer array sorted in ascending order. We want to find the index of the value $34$ with the binary search. The input array has nine elements with indices from $1$ to $9$. The target value $34$ has index $8$.

• First, we consider the entire array. The leftmost index is $1$, the rightmost one is $9$. The index of the middle element is $\frac{1 + 9}{2}=5$

• It's time to make some decisions. Our target element $34$ is greater than the middle element $24$. Because the array is sorted in ascending order, the left subarray cannot possibly contain the target element, so we continue the search in the right subarray.

• We consider the elements with indices from $6$ to $9$. The index of the middle element is $\frac{6+9}{2}=7$ (integer division).

• The target element $34$ is greater than the middle element $30$. Because the array is sorted in ascending order, we continue the search in the right subarray.

• This time we look at elements with indices from $8$ to $9$. The index of the middle element is $\frac{8+9}{2}=8$ (integer division).

Look what has happened: the target element $34$ matches the middle value $34$! Hence, we return the index $8$.

Pseudocode of the binary search function

function found_binary(array, value):
    left = 1                            // the starting value of the left border
    right = len(array)                  // the starting value of the right border
    while left <= right:                // while the left border is to the left 
                                        // of the right one (or if they match)
        middle = int((left+right)/2)    // finding the middle of the array (int removes
                                        // the fractional part)
        if array[middle] == value then: // if the value from the middle of the array 
                                        // is equal to the target one
            return middle               // returning the index of this element
        elif array[middle] > value then:// else if the value from the middle is greater 
                                        // than the target one
            right = middle - 1          // setting a new value to the right border (the one 
                                        // to the left of the middle one)
        else:                           // else (if the value from the middle is less than 
                                        // the target one)
            left = middle + 1           // setting a new value to the left border (the one 
                                        // to the right of the middle one)
    return -1                           // if the value is not found, we return -1

Conclusion

The binary search algorithm divides the array into two subarrays at each step and then searches for the element in one of them. The number of comparisons is much less than the length of the array.

If you would like to see a visualization of the algorithm, check this out; input a target value and click "Binary Search"!