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.
def binary_search(arr, x):
# Initialise left and right bounds of search to start and end of arr
left_index, right_index = 0, len(arr) - 1
# While left_index and right_index have yet to overlap
while left_index <= right_index:
# Find the midpoint between left_index and right_index
mid_index = (left_index + right_index) // 2
# If the element at mid_index is x, return mid_index
if arr[mid_index] == x:
return mid_index
# Otherwise, if x is greater than elem at mid_index,
# update left_index to be 1 above mid_index
elif arr[mid_index] < x:
left_index = mid_index + 1
# Otherwise, if x is less than elem at mid_index,
# update right_index to be 1 below mid_index
else:
right_index = mid_index - 1
# If x is not found, return -1
return -1
my_list = [2,3,4,5,6,7,8,9,10,11,12]
result = binary_search(my_list, 6) # 4

# 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

1. 1.
1. 1.
Rocket Academy solution code: https://pastebin.com/u7xC2K7t
2. 2.
Rocket Academy solution video: https://youtu.be/Z5VjCg2YuPs?t=1598

## 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/