Binary Search in Python: O(log n) Search Explained
Imagine searching for a word in a dictionary by starting in the middle, then jumping to the middle of whatever half remains. That's binary search. By halving the search space at each step, it finds a value in O(log n) time — a 1,000,000-element array needs at most 20 comparisons. Binary search is one of the most important algorithms you'll learn, and it appears constantly in coding interviews.
Prerequisite: the array must be sorted. Binary search exploits sorted order — without it, there's no way to know which half to discard.
How Binary Search Works: The Core Idea
Maintain two pointers, left and right, defining the current search window. At each step, check the middle element:
- If it equals the target → found it, return the index.
- If it's less than the target → target must be in the right half; move
leftup. - If it's greater than the target → target must be in the left half; move
rightdown.
Repeat until found or the window collapses (left > right).
Step-by-Step Walkthrough
# Array: [1, 2, 4, 5, 7, 9, 12], target = 7
# 0 1 2 3 4 5 6
# Step 1: left=0, right=6, mid=3 → nums[3]=5 < 7 → search right half
# Step 2: left=4, right=6, mid=5 → nums[5]=9 > 7 → search left half
# Step 3: left=4, right=4, mid=4 → nums[4]=7 == 7 → FOUND at index 4
3 comparisons instead of potentially 7 for a linear search. At scale, this difference is enormous.
Code Implementation
def binary_search(nums, value):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2 # integer division — always a valid index
if nums[mid] == value:
return mid # found — return the index
elif nums[mid] < value:
left = mid + 1 # target is in the right half
else:
right = mid - 1 # target is in the left half
return -1 # target not in array
# Examples:
print(binary_search([1, 2, 4, 5], 4)) # 2
print(binary_search([1, 2, 4, 5], 3)) # -1
print(binary_search([1, 2, 4, 7, 9], 1)) # 0 (first element)
print(binary_search([1, 2, 4, 7, 9], 9)) # 4 (last element)
Complexity Analysis
- Time: O(log n) — The search space halves with each comparison. An array of 1 billion elements needs at most 30 comparisons.
- Space: O(1) — Only two pointers, regardless of array size. No recursion, no extra data.
Edge Cases
# Empty array:
binary_search([], 5) # -1 (loop never runs)
# Single element — found:
binary_search([7], 7) # 0
# Single element — not found:
binary_search([7], 3) # -1
# Target at first position:
binary_search([1, 3, 5, 7], 1) # 0
# Target at last position:
binary_search([1, 3, 5, 7], 7) # 3
# Target not present:
binary_search([1, 3, 5, 7], 4) # -1
Critical Pitfalls to Avoid
- Using
(left + right) // 2for very large arrays: In Python this is fine (integers don't overflow). In languages like Java/C++, useleft + (right - left) // 2to prevent integer overflow. - Wrong loop termination —
<vs<=: Usewhile left <= right. A strict<misses the case whenleft == right(a one-element window), causing false negatives. - Off-by-one in pointer updates: After checking mid, move to
mid + 1ormid - 1— never justmid. Forgetting the ±1 creates an infinite loop.
Key Takeaways
- Binary search requires a sorted array and finds any value in O(log n) time.
- Maintain
leftandrightpointers; computemid = (left + right) // 2each iteration. - Adjust pointers with
left = mid + 1orright = mid - 1(never justmid). - Return
-1when the loop ends without finding the target.
What to Learn Next
Iterative binary search is the foundation. Next, learn the recursive version (Binary Search II) which builds identical logic using function calls instead of a loop. Then explore powerful binary search variations: finding the leftmost/rightmost occurrence of a duplicate value, searching a rotated sorted array, and using binary search on the answer (e.g., finding the minimum capacity to ship packages in D days).
