Binary Search:
Binary Search can only be applied to a sorted list. If the list is not sorted, add the time complexity of sorting to that of binary sort to determine the total complexity.
- Divide the list into two halves (left, center element, right)
- If element we are searching for is center element, stop
- If element is greater than center element, divide right half of list and repeat the steps
- If element is less than center element, divide left half of list and repeat the steps
Eg: Array 1 2 3 4 5 6 7 8 9 Find 1
Scan 1: Middle:1; 1<5 > Array: 1,2,3,4
Scan 2: Middle:2; 1<2 > Array: 1
Scan 3: Middle:1; 1=1 > Stop
Analysis of Binary Search
Recurrence T(n) = T(n/2) + c T(n/2) = T(n/4)+c
- T(n) = O(logn)
Implementation in python
#Note: Binary search only works when the list is sorted
def bsearch (seq, v, l, r):
if (r-l == 0):
return(False) #element not present
mid = (l+r)//2 #finding the middle element
if(v == seq[mid]): #if sequence equal to the middle element return true
return (True)
if (v < seq[mid]):
return (bsearch(seq,v,l,mid)) #search left half
else:
return (bsearch(seq,v,mid+1,r)) #search right half
If you are stuck at any point or have any doubts, drop a message here