Algorithm for Binary Search in C
Let be the element we are searching for and the array is sorted in the ascending order.
- Compare with the middle element of the array.
- If matches with the middle element, we return the index of the middle element.
- 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
- 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.
- 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.
C Program for Binary 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.