Binary Search
Searching: lesson 2 of 8
A million records, twenty guesses. Sorted data only.
Lesson 2 of 8 · 5 min
Binary Search
Step 1 of 7
target16probes0
mid
2
5
8
12
16
23
31
42
lo
hi
The array is sorted, so the middle element tells you which half the target cannot be in.
The Idea
On sorted data, compare the target with the middle element and throw away the half that cannot contain it. Repeat until one candidate remains. That halving gives you O(log n).
Real-World Example
Finding "Nadia" in your phone contacts. You never scroll from A; you jump near the middle, land somewhere around M, and instantly ignore everything before it. Two or three jumps later you are there.
The Code
def binary_search(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
lo = mid + 1 # target must be in the right half
else:
hi = mid - 1 # target must be in the left half
return -1
print(binary_search([2, 5, 8, 12, 16, 23], 16)) # 4Your turn
Fill in the blank.
nums = [1, 3, 5, 7, 9]
lo, hi = 0, 4
mid = (lo + hi) // 2
# nums[mid] is 5 and the target is 9 -> search right
lo = ___Mini quiz
1 / 3