Problem Statement
Binary Search
You are given a list of whole numbers called nums that is already sorted from smallest to largest, and one number called target. Your job is to find target in the list. If it is there, return the spot it sits at (its index, which is just its position counting from 0). If it is not there, return -1. There is one catch: your method has to be fast, fast enough to count as O(log n). O(log n) means that each step throws away half of what is left, so even a huge list only needs a few steps.
Translate the prompt
Given a sorted array and a target, return the index of the target or -1 if absent. Must run in O(log n).
Signals to notice
Brute force first
Linear scan from index 0 to the target. O(n) and ignores the sorted property.
The key insight
A sorted array tells you, at any midpoint, whether the target is to the left, right, or here. That lets each step discard half of the remaining positions.
Trace it on nums=[-1,0,3,5,9,12], target=9
lo=0 hi=5 mid=2 nums[2]=3 3 < 9 → lo=3 lo=3 hi=5 mid=4 nums[4]=9 9 == 9 → return 4
What must stay true
If the target exists, it lives in `nums[lo..hi]`. The window strictly shrinks every iteration.
Shape of the loop
lo, hi = 0, n-1 while lo <= hi: mid = lo + (hi - lo) // 2 if nums[mid] == target: return mid elif nums[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1
Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Using `(lo + hi) / 2` in languages where `lo + hi` can overflow a 32-bit integer. Use `lo + (hi - lo) / 2` instead.