# InterviewElements.com

Thursday, Jan 17th

Last update12:59:40 PM GMT

• REGISTER

## Binary Search

Binary Search algorithm is one of the simplest search algorithms. But it is applicable on sorted list.

Well, if we assume sorted list in ascending order, then we would compare the target element to the middle element. If not found, then we compare the target value and middle element value. If middle is greater, then we consider the above elements and repeat the same. If middle is lesser than target, then we apply same algorithm to the below list.

N -> number of elements; start -> the lower index of the array; end -> the end index of the array
```
BinarySearch(P[0..N-1], target, start, end)
{

if (end < start)
mid = (start + end)/2
if (P[mid] > target)
return BinarySearch(P, target, start, mid-1)
else if (P[mid] < target)
return BinarySearch(P, target, mid+1, end)
else
return mid // found
}```
Lets assume we have list of integers:  1, 5, 7, 8, 14, 17, 19, 27, 35, 40 and we have to search for: target->19
Here start is 0 and end is N-1, that is 9. Therefore, mid is 4.
So, in the first iteration: P[start]->1 ; P[end]->40 ; P[mid]->14
Since P[mid] < target, our list becomes 17, 19, 27, 35, 40
Similarly, in the next iteration the list would become 17, 19
And in the last iteration, just 19.
In this example, we make 4 comparisons. Is it the maximum number of comparisons ? Might be !

Time Complexity

The search space halves after each iteration. So, if we have 10 elements in our case, it bring down to 5 elements which breaks down to 2 elements and it finally to 1.
The time performance of binary search algorithm is O(logN). And number of comparisons is greatest integer less than (logN+1).