Binary Search
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
In a sorted list find the position of a target, or say it is missing, in O(log n).
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1Look at the middle element. What does it tell you about which half to keep?
- Hint 2Keep two markers, one at each end of the part still possible, and move them inward.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
You look up a word in a dictionary. You never start at page 1. You open the book in the middle: is your word before or after this page? That throws away half the book. Open the middle of the remaining half and repeat. A 1000-page dictionary needs only about 10 openings.
- The obvious way
Scan from the left until you find it: O(n).
- The key insight
In a sorted list one comparison with the middle removes half of what is left. After about log2(n) halvings only one spot remains. Keep the promise: if the target is present, it lies between the two markers.
- The algorithm
- Put one marker on the first item and one on the last.
- Look at the middle item between the markers.
- Equal to the target? Done. Too small? Move the left marker just past the middle. Too big? Move the right marker just before it.
- Markers crossed without a hit? The target is not there.
Watch it run
Examplenumbers = [-1, 0, 3, 5, 9, 12], target = 9
Open in the middle: 3. Our target 9 is bigger, so everything up to 3 is out.
still possible: [5, 9, 12]
Where people slip
- Move past the middle (middle + 1 / middle - 1); keeping it can loop forever.
- Write the middle as low + (high - low) / 2 in languages where the sum can overflow.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def search(nums, target):
low, high = 0, len(nums) - 1
while low <= high:
middle = (low + high) // 2
if nums[middle] == target:
return middle
if nums[middle] < target:
low = middle + 1 # target can only be to the right
else:
high = middle - 1 # target can only be to the left
return -1Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.