Bootcamp

Search…

A.6: Binary Search

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.

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

- 1.
- 1.
- 2.

- 1.
- 1.
- 2.

- 1.
- 1.Hint: Can we use binary search to find the factor of this number if it were a perfect square?

- 2.
- 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/

Binary Search Animation by Y. Daniel Liang

Last modified 4mo ago

Copy link

On this page

Introduction

Example Code

Exercises

Pre-Class

Part 1

More Comfortable

Further Reading