Embedded Systems

C program for binary search

C program for binary search

Binary search is generally employed on sorted array. Suppose you have sorted array and you want to search for a single element in array then a simple approach is to scan whole array to find particular element like this


The time complexity of above algorithm is O(n) because we scan whole array, as the number of element increase in array our searching time would also increase.



The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(Log n). We basically ignore half of the elements just after one comparison.
1) Compare element to search with the middle element.
2) If element matches with middle element, we return the mid index.
3) Else If element is greater than the mid element, then element can only lie in right half sub array after the mid element. So we recur for right half.
4) Else (element is smaller) recur for the left half.

C program for binary search


Suggested Reading