learningto/pass

Binary Search

EasyAlgorithms

Binary search is deceptively tricky: off-by-one errors are everywhere. Beyond sorted array search, master the generalized template for searching over a monotonic answer space.

AVG TIME
O(log n)
SPACE
O(1)
BEST
O(1)
WORST
O(log n)

Step-by-Step Walkthrough

step-by-step walkthrough

Binary Search

1 / 6
algorithm.py
1def binary_search(nums, target):
2 left, right = 0, len(nums) - 1
3
4 while left <= right:
5 mid = (left + right) // 2
6
7 if nums[mid] == target:
8 return mid
9 elif nums[mid] < target:
10 left = mid + 1
11 else:
12 right = mid - 1
13
14 return -1
visualization
array
1
0
L
3
1
5
2
7
3
9
4
11
5
13
6
15
7
17
8
19
9
R
variable inspectorO(1) setup
nums=[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
target=13
left=0
right=9
mid=None
The Setup - Sorted Array Required
Binary search only works on a SORTED array. We have [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] and we're looking for 13. We start with two pointers: left at index 0, right at the last index (9).
speedmed
← →space

In Python

Concept to Code- 2 structures for this topic
declare
nums = [1, 2, 3]
common ops
nums.append(x)
O(1)
nums.pop()
O(1)
nums[i]
O(1)
nums.insert(i, x)
O(n)
x in nums
O(n)
nums.sort()
O(n log n)
len(nums)
O(1)
say in interview
"I'll use an array to store the elements"
Python lists ARE dynamic arrays (like ArrayList in Java), NOT linked lists. Access by index is O(1).

Math You Need For This

Imagine a 30-level building with n=1,000,000,000 rooms, one per floor. Binary search: go to floor 500,000,000. Too high? Go to floor 250,000,000. Each elevator ride halves the search space. You find any room in 30 rides.

Required concepts
Key math ideas
1 / 2

Logarithms - "how many times can you cut in half?"

log₂(n) answers this question: if you start with n things and keep cutting the group in half, how many cuts until you reach 1? For 1,024 items that is only 10 cuts. For a million items it is about 20. The number barely grows even as n explodes.

Remaining1024 items (log₂(1024) = 10)
Clicks so far: 0

Think of it this way: A phone book with 1,024 names. Flip to the middle - is your name before or after? Flip to the middle of the surviving half. Repeat. You find any name in at most 10 flips, not 1,024.

For algorithms: Any algorithm that cuts its remaining work in half each step runs in O(log n). Binary search, balanced tree lookups, and heap operations all work this way.

Interactive 3D Visualization

Array
Access: O(1)Search: O(n)Space: O(n)
Drag to orbit - Scroll to zoom

Brute Force vs Optimized

Interview Strategy - Search in Sorted Array

Start brute force, explain it, THEN optimize. "I can see a straightforward approach. Let me start there, then we can optimize."

Brute Force
Linear Scan
TimeO(n)
SpaceO(1)

"Check every element one by one until you find the target."

Pros
  • +Works on unsorted arrays too
  • +Simple to implement
Cons
  • -Does not take advantage of sorted order
  • -Slow for large arrays
Optimized
Binary Search
TimeO(log n)
SpaceO(1)

"Cut the search space in half each step. Only works on sorted data."

Pros
  • +Extremely fast - log(1,000,000) = only 20 steps
  • +No extra space needed
  • +Classic interview pattern
Cons
  • -Only works if data is sorted
  • -Off-by-one errors are common
The Tradeoff

No space tradeoff here - both are O(1) space. The optimization comes from exploiting the sorted property. This is free performance.

For n=1,000,000
Brute Force1,000,000 ops
Optimized20 ops
Say This

Say: "Since the array is sorted, we can use binary search to cut the problem in half each step, going from O(n) to O(log n)."

Watch It Run

Binary Search
Cut the search space in half each step. O(log n) on sorted arrays.
SPEED
1 / 5
Your data
algorithm.py
1>def binary_search(nums, target):
2  left, right = 0, len(nums) - 1
3  while left <= right:
4  mid = (left + right) // 2
5  if nums[mid] == target:
6  return mid
7  elif nums[mid] < target:
8  left = mid + 1
9  else:
10  right = mid - 1
11  return -1
array visualization
1[0]
3[1]
5[2]
7[3]
9[4]
11[5]
13[6]
0
1
2
3
4
5
6
i

We're searching for target=7 in nums=[1, 3, 5, 7, 9, 11, 13]. The array is sorted - that's the prerequisite for binary search. Without sorted order, this algorithm breaks.

VariablesStep 1 of 5 (setup)
nums=[135791113]
target=7
Spaceplay/pause← →step+ -speed

Python Implementation

example.py
Loading...
Now try it yourself
2 challenges with test cases and AI feedback
Practice Now

Complexity Analysis

1481216n²nlog n1n (input size)
COMMON OPERATIONS
Array
Access:O(1)
Search:O(n)
Insert end:O(1)*
Insert mid:O(n)
Hash Map
Get/Set:O(1)*
Delete:O(1)*
Search value:O(n)
Iterate:O(n)
Linked List
Access:O(n)
Search:O(n)
Insert head:O(1)
Delete known:O(1)
Binary Search
Search:O(log n)
Insert:O(log n)
Balanced BST
Search:O(log n)
Insert:O(log n)
Delete:O(log n)
Heap
Peek min/max:O(1)
Push:O(log n)
Pop:O(log n)
Heapify:O(n)
Graph (BFS/DFS)
Traversal:O(V+E)
Dijkstra (heap):O((V+E) log V)
Merge / Quick Sort
Sort:O(n log n)
Space (merge):O(n)
Space (quick):O(log n)

* amortized average case

READY TO TEST YOURSELF?

Put Binary Search into practice

The best way to lock in what you've learned is to write code. Solve real interview-style problems right now.

Binary Search
Next: Recursion & Backtracking