Binary search is a divide and conquer strategy to find an element in a sorted list. The binary search is not feasible for unsorted array.Let us consider following array data:

{17,18, 19, 27, 46, 78, 102, 114}
Then how can we find if an element present in the above list? For example to find 19 we would proceed with below steps.

calculate the middle element , in given example 46 is middle element
compare the middle element with the target(19) element
here 19 is less than 46.
if target is equal to the middle element, then return the found index.
if target(19) is less than middle element(46) , then search from index 0 to index (middle -1)
if target is greater than middle element , then search from index (middle +1) to up to last index.

Complexity analysis of binary search algorithm

Best case performance O(1)
Average case performance O(log n)
Worst case space complexity O(1)
Worst case performance O(log n)

Sample c code for binary search algorithm

Sample c++ code for binary search algorithm


Related Contents to follow