Bootcamp
Search…
A.6: Binary Search

Introduction

Binary search allows us to search a sorted array for a target number in O(log(n)) time. This is faster than linear search, which runs in O(n) time. Note that we can only apply binary search on sorted arrays; it does not work on unsorted arrays.

Example Code

Consider the following canonical binary search implementation.
1
def binary_search(arr, x):
2
# Initialise left and right bounds of search to start and end of arr
3
left_index, right_index = 0, len(arr) - 1
4
# While left_index and right_index have yet to overlap
5
while left_index <= right_index:
6
# Find the midpoint between left_index and right_index
7
mid_index = (left_index + right_index) // 2
8
# If the element at mid_index is x, return mid_index
9
if arr[mid_index] == x:
10
return mid_index
11
# Otherwise, if x is greater than elem at mid_index,
12
# update left_index to be 1 above mid_index
13
elif arr[mid_index] < x:
14
left_index = mid_index + 1
15
# Otherwise, if x is less than elem at mid_index,
16
# update right_index to be 1 below mid_index
17
else:
18
right_index = mid_index - 1
19
# If x is not found, return -1
20
return -1
21
22
my_list = [2,3,4,5,6,7,8,9,10,11,12]
23
result = binary_search(my_list, 6) # 4
Copied!

Exercises

Pre-Class

  1. 1.
    1. 1.
      Rocket Academy solution code: https://pastebin.com/9v2GdhRM​
    2. 2.
      Rocket Academy solution video: https://youtu.be/Z5VjCg2YuPs?t=1147​

Part 1

More Comfortable

  1. 1.
    1. 1.
      Hint: Can we use binary search to find the factor of this number if it were a perfect square?
  2. 2.
    1. 1.
      Hint: Heaps may be helpful. Consider the solution to this heaps problem that we may have solved in D.5.8: Heaps: https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/​

Further Reading

Binary Search Animation by Y. Daniel Liang