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 binarySearch(arr, x):
2
# Initialise left and right bounds of search to start and end of arr
3
left_index, right_index = 0, len(x) - 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
20
return -1
21
22
mylist = [2,3,4,5,6,7,8,9,10,11,12]
23
result = binarySearch(my_list, 6) # 4
Copied!

# Exercises

1. 1.
1. 1.
2. 2.

1. 1.
1. 1.
2. 2.

## 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/โ