Binary search

Binary search is a fast and efficient search algorithm where an ordered and sorted input is recursively bisected (with the “bad” half discarded) until the result of the search remains.

Efficiency

Binary search is O(log n) (logarithmic time/space) in Big O notation. Given n elements in the input, completing the search will take (at most) log2 * n steps. So, given 8 elements, the search will take (at most) 3 steps.

Requirements

• Input must be ordered and sorted

Implementation

Pseudocode:

list = ordered_and_sorted_list
low = 0
high = list.length - 1
match = what_i_want

while low <= high
  mid = (low + high) / 2
  
  if mid == match: return mid
  
  if mid > match: high = mid - 1
  
  if mid < match: low = mid + 1

Python (recursive):

def binary_search(arr, low, high, match):
  mid = (high + low) // 2
  
  if arr[mid] == match:
    return mid
  elif arr[mid] > match:
    return binary_search(arr, low, mid - 1, match)
  else:
    return binary_search(arr, mid + 1, high, match)

# Test
arr = [1, 3, 4, 7, 11]
low = 0
high = len(arr) - 1
match = 7

result = binary_search(arr, low, high, match)