Binary Search
Binary search algorithm can be used over a sorted container
The time complexity provided by binary search algorithm is O(log n), which is quite efficient compared to the linear search O(n) algortihm
Binary search also plays as a vital sub routine in bigger algorithmic problems
pseudo code for binary search:
given sorted container A, search element x
left = 0, right = len(A)-1
while left <= right:
mid = left + (right-left)/2
if x == A[mid]:
print("found")
break;
elif x < A[mid]:
# search in left side
right = mid-1
else:
# search in right side
left = mid+1
if left > right:
print("not found")
