Binary search turns O(n) lookups into O(log n) on sorted data. The two-pointer and sliding-window patterns bring many array and string problems down from O(n²) to O(n). Three techniques you will reuse constantly.
On sorted data you never scan linearly — you look at the middle, discard half based on the comparison, and repeat, reaching the answer in O(log n). The precondition is that the data is sorted (or monotonic in some property). Getting the boundary conditions right is the whole game; internalize one correct template and reuse it.
# find target in a SORTED list -> index, or -1. O(log n).
def binary_search(a, target):
lo, hi = 0, len(a) - 1
while lo <= hi:
mid = (lo + hi) // 2
if a[mid] == target:
return mid
elif a[mid] < target:
lo = mid + 1 # target is in the right half
else:
hi = mid - 1 # target is in the left half
return -1
# each step HALVES the range: 1,000,000 items -> ~20 comparisons.
# Python's bisect module gives this for free: bisect.bisect_left(a, x).Binary search is not just for finding a value in a list — it works on any monotonic condition. When a problem asks for the minimum/maximum value that satisfies some "is this feasible?" check, and feasibility only flips once as the value grows, you can binary-search the answer space. This turns many optimization problems from O(n²) trial-and-error into O(n log n).
# pattern: find the smallest x where feasible(x) becomes True.
def binary_search_answer(lo, hi, feasible):
while lo < hi:
mid = (lo + hi) // 2
if feasible(mid):
hi = mid # mid works -> answer is mid or smaller
else:
lo = mid + 1 # mid too small -> go higher
return lo
# e.g. "minimum ship capacity to ship all packages in D days":
# feasible(cap) = can we finish within D days at this capacity? (monotonic)
# works whenever the yes/no answer flips exactly once as x increases.The two-pointer pattern walks two indices through data — often from both ends inward, or one chasing the other — to solve in one O(n) pass what looks like it needs nested loops. On a sorted array, converging pointers find a pair summing to a target without the O(n²) double loop; the same idea reverses arrays, removes duplicates, and merges sequences.
# pair summing to target in a SORTED array — O(n), O(1) space
def two_sum_sorted(a, target):
lo, hi = 0, len(a) - 1
while lo < hi:
s = a[lo] + a[hi]
if s == target:
return [lo, hi]
elif s < target:
lo += 1 # need a bigger sum -> move left pointer up
else:
hi -= 1 # need a smaller sum -> move right pointer down
return None
# the nested loop (O(n^2)) collapses to one converging pass (O(n)).A sliding window maintains a contiguous range over an array or string, expanding and shrinking its ends to track a running property (a sum, a set of characters). It answers "best/longest/shortest subarray satisfying X" in a single O(n) pass instead of checking every subarray in O(n²). Recognizing "contiguous subarray/substring" in a problem is the cue to reach for it.
# longest substring with no repeating characters — O(n)
def longest_unique(s):
seen = set()
left = 0
best = 0
for right in range(len(s)):
while s[right] in seen: # shrink from the left until valid
seen.remove(s[left])
left += 1
seen.add(s[right]) # expand the window to the right
best = max(best, right - left + 1)
return best
longest_unique("abcabcbb") # 3 ("abc")
# each element enters + leaves the window once -> O(n), not O(n^2).