Algorithm for Binary Search in C

Let  be the element we are searching for and the array is sorted in the ascending order.

1. Compare  with the middle element of the array.
    
2. If  matches with the middle element, we return the index of the middle element.
    
3. Else if  is greater than the middle element, it means that  can only lie in the right half subarray after the middle element. So we repeat steps 1 and 2 for the right half subarray and leave the left half subarray from the algorithm
    
4. Else if  is smaller than the middle element, it means that  can only lie in the left half subarray before the middle element. So, we repeat steps 1 and 2 for the left half subarray.
    
5. We will keep doing that till we find  or there is no element left in the subarray being considered.

As we can see, the binary search ignores the half elements of the subarray after each pass. Due to this, it is able to reduce the time required for searching the element in the array as compared to linear search.

In this article, we will understand the Binary search algorithm and how to write binary search programs in C. We will see both iterative and recursive approaches and how binary search is able to reduce the time complexity of the search operation as compared to linear search.