Search

The standard binary search template. Foundation for all logarithmic search problems.

lo, hi = 0, len(a) - 1
while lo <= hi:
    mid = lo + (hi - lo) // 2
    if a[mid] == target: return mid
    elif a[mid] < target: lo = mid + 1
    else: hi = mid - 1

Safe midpoint calculation prevents integer overflow. Critical for correct binary search.

mid = lo + (hi - lo) // 2

Left boundary search finds the first occurrence. Key for range queries and count problems.

lo, hi = 0, len(a)
while lo < hi:
    mid = lo + (hi - lo) // 2
    if a[mid] < target: lo = mid + 1
    else: hi = mid
return lo

Right boundary search finds the insertion point after equals. Paired with bisect_left for range counting.

lo, hi = 0, len(a)
while lo < hi:
    mid = lo + (hi - lo) // 2
    if a[mid] <= target: lo = mid + 1
    else: hi = mid
return lo

bisect_left gives the insertion index directly. Foundation for sorted-container operations.

import bisect
pos = bisect.bisect_left(a, target)
# pos is the insert index

heappush maintains the min-heap invariant. Used in merge-k-lists and streaming median.

import heapq
heapq.heappush(h, val)

heappop extracts the minimum. Pair with heappush for priority queue operations.

import heapq
heapq.heappop(h)

heapify converts a list to a heap in O(n). Faster than n individual pushes.

import heapq
heapq.heapify(a)

nlargest uses a min-heap of size k internally. O(n log k) for top-k problems.

import heapq
top_k = heapq.nlargest(k, a)

Priority queues power Dijkstra's algorithm and task scheduling problems.

import heapq
heapq.heappush(h, (priority, item))
_, item = heapq.heappop(h)

lo<=hi for exact match (3 outcomes). lo<hi for boundary finding (2 outcomes, converges). Pick the right template.

BINARY SEARCH TEMPLATES — WHEN TO USE WHICH
────────────────────────────────────────────
TEMPLATE 1: lo <= hi (exact match)
  lo, hi = 0, n - 1
  while lo <= hi:
      mid = (lo + hi) // 2
      if a[mid] == target: return mid
      elif a[mid] < target: lo = mid + 1
      else: hi = mid - 1
  return -1  # not found
  → Use for: exact value search
  → Terminates: lo > hi (empty range)

TEMPLATE 2: lo < hi (converge to answer)
  lo, hi = 0, n - 1
  while lo < hi:
      mid = (lo + hi) // 2
      if condition(mid):
          hi = mid       # mid could be answer
      else:
          lo = mid + 1   # mid is not answer
  return lo  # lo == hi == answer
  → Use for: first/last position, min satisfying condition
  → Terminates: lo == hi (single candidate)

GOTCHA: use mid = (lo + hi + 1) // 2 when
        lo = mid (not mid+1) to avoid infinite loop

Heap is better than sorting when k << n. Quickselect is O(n) average but doesn't order results.

HEAP vs SORTING FOR TOP-K
─────────────────────────
SORTING:
  sorted(a)[-k:]           # O(n log n) time, O(n) space
  + Simple code
  + Get all elements in order
  - Must process all elements upfront

MIN-HEAP of size k:
  import heapq
  heapq.nlargest(k, a)     # O(n log k) time, O(k) space
  + Better when k << n
  + Can process stream (online)
  + O(k) space

MAX-HEAP (negate values):
  heap = [-x for x in a]
  heapq.heapify(heap)      # O(n)
  top = -heapq.heappop(heap)

QUICKSELECT:
  O(n) average for kth element
  + Fastest average case
  - O(n²) worst case
  - Doesn't sort the top k

DECISION:
  k close to n?        → just sort
  k << n?              → min-heap of size k
  Only need kth value? → quickselect
  Stream of elements?  → heap (must be online)

Binary search for the largest integer whose square <= x. Return hi (not lo) because lo overshoots by 1.

lo, hi = 0, x
while lo <= hi:
    mid = (lo + hi) // 2
    if mid * mid <= x:
        lo = mid + 1
    else:
        hi = mid - 1
return hi

Move toward the higher neighbor — a peak must exist on that side. Uses lo < hi (not <=) and hi = mid (not mid-1).

lo, hi = 0, len(a) - 1
while lo < hi:
    mid = (lo + hi) // 2
    if a[mid] < a[mid + 1]:
        lo = mid + 1
    else:
        hi = mid
return lo