Binary Search

When solving a search problem, we should think of binary search whenever the data set is sorted in some way.

Even if the dataset is not sorted, we should still think of binary search if the data is sortable. It depends on if sorting the data first will make a better & faster solution.

Any dataset is sortable if you can directly compare any two items from the dataset, i.e., we should be able to decide which one is “smaller” or which one is “larger”. Examples:

• numbers (integer, float, etc)
• words (strings): alphabetical order or any other defined comparison
• products: by price, by ratings, by weight, etc
• music albums: by titles, by review scores, by release years, by total minutes, etc
• NBA players: by number of rings, by career average scores, by career total scores, by career total assists, etc

Obviously “smaller” and “larger” can mean many more different things.

For binary search, we also need to access to the medium value immediately.

In summary, to apply binary search, the conditions are:

1. To compare any two value easily.
2. To access to the medium value in any range easily.

Here “easily” means no significant cost. So you can see the dataset doesn’t even has to be “sorted”. For example, if we have APIs to help achieve the above two requirements, that’s good enough.

def compare(v1, v2):
  # tell me whether v1 is "smaller" than v2
def get_medium(dataset, range):
  # give me the medium value from the dataset in the specific range

The simplest example is to search a number from a sorted integer list. Here it’s pretty straightforward:

def compare(v1, v2):
  return v1 < v2
def get_medium(number_list, start_index, end_index):
  if start_index > end_index:
    return None
  mid_index = (start_index + end_index) // 2
  return number_list[mid_index]

Now let’s go to the core algorithms of binary search. Given an integer list num_listand the target number target.

A recursive solution:

def bs_helper(num_list, start, end, target):
  if start > end:
    return None
  mid = (start + end) // 2
  if num_list[mid] == target:
    # Found it!
    return mid
  if num_list[mid] > target:
    # Any number after mid must be also larger than it
    end = mid - 1
    return bs_helper(num_list, start, end, target)
  else:
    # Any number before mid must be also smaller than it
    start = mid + 1
    return bs_helper(num_list, start, end, target)
def binary_search(num_list, target):
  start, end = 0, len(num_list) - 1
  return bs_helper(num_list, start, end, target)

The non-recursive solution is not more difficult.

def binary_search(num_list, target):
  start, end = 0, len(num_list) - 1
  while start < end:
    mid = (start + end) // 2
    if num_list[mid] == target:
      return mid
    if num_list[mid] > target:
      end = mid - 1
    else:
      start = mid + 1
  return None