Search — Micro Drills

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

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

47 Midpoint without overflow 5s

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

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

48 Left boundary (bisect_left) 15s

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

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

49 Right boundary (bisect_right) 15s

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

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

50 Search insert position 10s

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

68 Heappush 5s

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

import heapq
heapq.heappush(h, val)

69 Heappop 5s

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

import heapq
heapq.heappop(h)

70 Heapify a list 5s

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

import heapq
heapq.heapify(a)

71 K largest elements 10s

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)

72 Heap as priority queue 10s

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

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

273 Integer square root (bisect) 10s

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

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

274 Find peak element (binary search) 10s

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 &lt; hi:
    mid = (lo + hi) // 2
    if a[mid] &lt; a[mid + 1]:
        lo = mid + 1
    else:
        hi = mid
return lo