Binary Search

Overview#

  • Time complexity - O(logn)
  • Space complexity - O(1) for iterative, O(logn) for recursive

General Idea#

Binary search is one of the most commonly used search algorithm on sorted arrays. To search in a sorted array for a specific element, we can repeatedly divide the search range into half.

For example, in the first run, the range is the whole array. If the search key is less than the value at the middle of the array, then the element would be found on the "left" side of the array. Conversely, if the search key is more than the value at the middle of the array, the element would be found on the "right".

"Left" and "right" here refers to the first half and the second half of the array respectively. We repeatedly search in this manner till we find the element or till the interval range is zero.

Iterative Implementation#

# Returns the index of the array where search key was found
# If no element found, returns -1
def binary_search(arr, key):
left = 0
right = len(arr) - 1
while(left <= right):
mid = (left + right) // 2
# check for key
if(arr[mid] == key):
return mid
elif(arr[mid] < key):
left = mid + 1
else:
right = mid - 1
return -1

Recursive Implementation#

# Returns the index of the array where search key was found
# If no element found, returns -1
def binary_search(arr, left, right, key):
# base case
if(right >= left):
mid = (left + right) // 2
# check for key
if(arr[mid] == key):
return mid
elif(arr[mid] > key):
return binary_search(arr, left, mid - 1, key)
else:
return binary_search(arr, mid + 1, right, key)
else:
return -1