Friday, Jan 19th

Last update12:59:40 PM GMT

Binary Search

Write e-mail

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

argaiv1077

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)
     return -1 // not found
 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).


Share this post



Add comment

Please refrain from using slang or abusive language in the comments.
To avoid waiting for your comment to be published after being reviewed, please log in as a registered user.


Security code
Refresh

Web Hosting