Binary Search

Binary Search is a method of searching an element in a sorted list of items. It follows the divide and conquer approach. The list is divided into two halves. The key(element to be searched) is compared with the middle element of list. If the element is found the index is returned, else, the element is searched in either of the sub-list until found or the last sub-list(only one element remaining) is visited. 

Illustration:

Algorithm:

1. Initialize the sorted list, set low=0 and high=length(list)-1
2. Set mid=low+(high-low)//2
3. Compare key with element at mid
4. If list[mid]==key, then return mid
5. Else if list[mid]>key, then low=low and high=mid-1
6. Repeat from 2 till list[mid]=key, else return= -1
7. Else low=mid+1 and high=high
8. Repeat from 2  till list[mid]=key, else return=-1
9. If return = -1, then print "Not found"
10. End

Time Complexity:

• Worst Case: O(log n) 
• Average Case: O(log n)
• Best Case: O(1)

Space Complexity: O(1)

Program for Binary Search