Binary Search
Search for a target value in a sorted array efficiently
Given a sorted array of integers nums and an integer target, return the index of target if it is in nums, or -1 if it is not. You must write an algorithm with O(log n) runtime complexity.
R — READ
READ
What does 'O(log n) runtime' mean for algorithm choice?
The constraint hints at binary search. The array is sorted, which enables halving the search space. Return -1 if not found.
Do you recognize that O(log n) points to binary search? Do you notice the sorted array?
Using linear search (O(n)) when the problem explicitly asks for O(log n).
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4 (nums[4] == 9)
Input: nums = [-1,0,3,5,9,12], target = 13
Output: -1
O — OBSERVE
OBSERVE
Why does binary search work here?
The array is sorted. At each step, we can eliminate half the remaining elements by comparing mid to target.
Do you understand why mid comparison lets us throw away half the array?
Thinking binary search requires recursion or memorizing exact code.
Example: [-1, 0, 3, 5, 9, 12], target = 9
• left=0, right=5, mid=2, nums[2]=3. 3 < 9, move left to 3.
• left=3, right=5, mid=4, nums[4]=9. Found! Return 4.
Each comparison halves the search space. log₂(6) ≈ 3 steps max.
P — PSEUDOCODE
PSEUDOCODE
What's my step-by-step binary search plan?
Initialize left and right pointers. While they don't cross, compute mid and compare.
Clear understanding of pointer movement.
Pseudocode with off-by-one errors in boundary conditions.
1. Initialize left = 0, right = len(nums) - 1
2. While left <= right:
a. Compute mid = (left + right) // 2
b. If nums[mid] == target, return mid
c. If nums[mid] < target, move left = mid + 1
d. If nums[mid] > target, move right = mid - 1
3. If loop ends, target not found. Return -1.
I — IMPLEMENT
IMPLEMENT
How do I write binary search without off-by-one errors?
Be careful with mid calculation and boundary updates.
Correct handling of loop condition and pointer updates.
Using (left + right) / 2 without integer division, or wrong boundary updates.
def search(nums, target):
"""
Search for target in a sorted array using binary search.
Args:
nums: Sorted list of integers
target: Value to find
Returns:
Index of target, or -1 if not found
"""
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
T — TEST
TEST
Does my code work on all cases?
Test: found at start/middle/end, not found, single element, negative numbers.
Thoroughness and edge case handling.
Only testing when the target is found.
Test 1: [-1,0,3,5,9,12], target=9 → 4 ✓
Test 2: [-1,0,3,5,9,12], target=13 → -1 ✓
Test 3: [5], target=5 → 0 ✓
Test 4: [5], target=1 → -1 ✓
Test 5: [-1,0,3,5,9,12], target=-1 → 0 (start) ✓
Test 6: [0], target=0 → 0 ✓
A — ANALYZE
ANALYZE
Why is this O(log n)?
Each iteration eliminates half the search space. After k iterations, we've narrowed down to n/(2^k) elements. When this reaches 1, we're done. k = log₂(n).
Understanding why binary search is logarithmic.
Claiming O(n) or not explaining the halving.
Why: Each comparison eliminates half the remaining elements. With n elements, we need at most log₂(n) comparisons. We use only a few variables (left, right, mid), so space is O(1).
Compare: Linear search is O(n). For 1 million elements, binary search needs ~20 steps; linear search needs up to 1 million.