PYTHON / DATA STRUCTURES AND ALGORITHMS
Binary search and the two-pointer technique
Implement binary search with a correct loop invariant, use bisect for insertion points, and solve sorted-array problems with converging or same-direction pointers.
What you will learn
- Write a lower-bound binary search using a half-open [lo, hi) interval
- Use bisect_left and bisect_right to locate duplicates and insertion points
- Solve pair-sum style problems with two converging pointers in one O(n) pass
- Use a read/write pointer pair to rewrite a list in place without extra memory
Understanding Binary search and the two-pointer technique
Binary search is not really about halving a list; it is about maintaining an invariant strong enough that you can discard everything on one side without looking at it. In the lower-bound form below the invariant is: every index before lo is known to hold a value less than the target, and every index from hi onward is known to hold a value greater than or equal to it. The answer must therefore lie in [lo, hi), and when that window becomes empty lo is exactly the first position where the target could be inserted. Writing the interval half-open is what makes the loop condition lo < hi and the update hi = mid consistent, with no off-by-one adjustment anywhere.
The O(log n) cost depends on being able to jump to the middle element in constant time, which is why binary search belongs to arrays and Python lists rather than linked structures. Walking to the middle of a linked list costs O(n) by itself, so halving buys nothing. The same requirement explains why bisect_left and bisect_right in the standard library take a sequence: they index it directly. bisect_left returns the first position holding the target, bisect_right the position just past the last one, so their difference is the number of occurrences, computed without scanning the run.
The two-pointer technique replaces search with a monotonic sweep. In the converging form, i starts at the left end and j at the right end of a sorted list, and each comparison rules out one whole candidate: if a[i] + a[j] is too small, then a[i] paired with the largest remaining partner still falls short, so a[i] cannot participate at all and i moves right. Each index moves only in one direction and they meet once, giving O(n) total work with no extra memory. The same-direction form, one slow write pointer trailing a fast read pointer, uses that one-way motion to compact or filter a list in place, because the write pointer can never overtake the read pointer and so never clobbers unread data.
def lower_bound(a, target):
lo, hi = 0, len(a) # answer lies in the half-open window [lo, hi)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < target:
lo = mid + 1 # mid is too small, so it cannot be the answer
else:
hi = mid # mid might be the answer, keep it in the window
return lo
data = [1, 3, 3, 3, 7, 9, 11]
for t in (0, 3, 4, 11, 12):
i = lower_bound(data, t)
print(t, i, data[i] if i < len(data) else None)
import bisect
print(bisect.bisect_left(data, 3), bisect.bisect_right(data, 3))Both techniques work by maintaining an invariant that lets you discard part of the input without ever examining it.
Worked examples
Converging pointers for a pair sum
Finds two values in a sorted list adding to a target, printing every step so the pointer motion is visible.
def pair_sum(a, target):
i, j = 0, len(a) - 1
while i < j:
s = a[i] + a[j]
print(f"i={i} j={j} sum={s}")
if s == target:
return (a[i], a[j])
if s < target:
i += 1
else:
j -= 1
return None
nums = [2, 4, 6, 9, 13, 20]
print(pair_sum(nums, 22))
print(pair_sum(nums, 5))Example explained
Line 1while i < j stops when the pointers meet, so no element is ever paired with itself.
Line 2s < target increments i because a[i] with the biggest partner left is already too small.
Line 3s > target decrements j because a[j] with the smallest partner left is already too big.
Line 4The 5 search prints five lines, one per discarded candidate, not 6*5/2 pairs.
Read and write pointers compacting in place
Removes duplicates from a sorted list in place using a slow write pointer behind a fast read pointer.
def dedup(a):
if not a:
return 0
write = 1
for read in range(1, len(a)):
if a[read] != a[write - 1]:
a[write] = a[read]
write += 1
return write
nums = [1, 1, 2, 2, 2, 5, 8, 8]
k = dedup(nums)
print(k, nums[:k], nums)Example explained
Line 1a[write - 1] is the last value already kept, so comparing against it detects a repeat.
Line 2write only advances on a new value, so it always trails read and never overwrites unread data.
Line 3The function returns a length, not a new list; nums[:k] is the meaningful prefix.
Line 4The tail of nums past index k is leftover garbage, which is the price of avoiding an allocation.
bisect_right as a threshold lookup
Maps a numeric score to a band by binary searching a sorted list of cut-off values.
import bisect
thresholds = [60, 70, 80, 90]
bands = ["F", "D", "C", "B", "A"]
def grade(score):
return bands[bisect.bisect_right(thresholds, score)]
for s in (59, 60, 79, 89, 90, 100):
print(s, grade(s))Example explained
Line 1bisect_right counts how many thresholds are less than or equal to score, which is exactly the band index.
Line 2bands has one more entry than thresholds, so every returned index is valid, including len(thresholds).
Line 3Using bisect_left instead would put a score of exactly 60 in F, since it returns the index of 60 itself.
Line 4The lookup stays O(log n) as the threshold table grows, unlike a chain of if statements.
Important notes
Python integers are arbitrary precision, so (lo + hi) // 2 cannot overflow here; the lo + (hi - lo) // 2 form you see in C and Java is unnecessary.
bisect accepts a key argument only from Python 3.10 onward; on older versions search a separate list of extracted keys instead.
Common mistakes
Mixing conventions by writing while lo <= hi together with hi = mid: when mid equals lo the window stops shrinking and the loop spins forever.
Writing lo = mid instead of lo = mid + 1 after ruling mid out, which hangs on two-element windows because mid keeps landing on lo.
Running a converging two-pointer scan on an unsorted list: it returns a wrong answer silently, since moving a pointer is only justified by the ordering.
Assuming bisect_left means found: on a miss it returns an insertion point, so you must check i < len(a) and a[i] == target before trusting it.
Try it yourself
Change, predict, then run
Given a sorted list that includes negative numbers, such as [-7, -3, -1, 0, 2, 5], produce the sorted list of their squares in a single O(n) pass by comparing the absolute values at both ends and filling a result list from the back.
Open the Python workspaceCheck your understanding
In the converging two-pointer pair-sum scan on a sorted list, when a[i] + a[j] < target you increment i. Why is discarding a[i] safe?
- Because a[i] is the smallest remaining value, and the smallest value can never belong to a valid pair.
- Because the list is sorted, so a[i] + a[j] is always the smallest sum still available.
- Because a[j] is the largest remaining partner, so a[i] falls short with every partner still in range.
- Because incrementing i keeps the remaining window an even number of elements.
Show answer
a[i] has just been tested against the largest partner left and still came up short; every other remaining partner is smaller, so no pair containing a[i] can reach the target. Option 0 is tempting but wrong: being the smallest value is not disqualifying on its own, and a[i] would still be the smallest if the sum had been too large, in which case you move j instead.