Skip to main content

Binary Search, Heaps, and Intervals

Binary search works on sorted arrays or monotonic functions (condition flips from false → true).

  • Repeatedly halve the search space using mid.
  • Check the condition at mid to decide whether to search left or right. Very common in interview problems where you “search for an answer” rather than an exact value.

1. Standard binary search (Exact match)

Idea: Search for a target in a sorted array.

def binary_search(arr, target): l, r = 0, len(arr) - 1 while l <= r: mid = (l + r) // 2 if arr[mid] == target: return mid elif arr[mid] < target: l = mid + 1 else: r = mid - 1 return -1

2. Lower bound/upper bound (Search insert position)

Idea: Find first/last position where a condition is true. Lower bound: first index ≥ target Upper bound: first index > target

def lower_bound(arr, target): l, r = 0, len(arr) while l < r: mid = (l + r) // 2 if arr[mid] >= target: r = mid else: l = mid + 1 return l

3. Binary search on answer (Parametric search)

Idea: Use binary search when the answer lies in a range and condition is monotonic.

When solving problems with binary search on the answer, you need to choose a search range [low, high].
This range comes from the domain of the answer (time, speed, capacity, distance — not array indices).

Step 1: Pick a trivial lower bound (low)
Choose the smallest possible answer:

  • Often 0 or 1.
  • Sometimes max(item) (e.g., if each machine must handle at least the biggest task).

Step 2: Pick an obviously feasible upper bound (high)
Choose a value that definitely works, even if it’s inefficient:

  • sum(items) → one worker/machine does everything.
  • The full span of coordinates.
  • A very large sentinel like 1e18.

Step 3: Make sure feasible(x) is monotonic
Your feasibility check should behave like this:

  • If feasible(x) is true, then feasible(x + 1) should also be true.
  • If feasible(x) is false, then feasible(x - 1) should also be false.

👉 In short:

  • Low = smallest possible valid answer.
  • High = a value that definitely works.
    Then binary search between them.
def binary_search_answer(low, high): while low < high: mid = (low + high) // 2 if condition(mid): # can we achieve with mid? high = mid else: low = mid + 1 return low

Time complexity: O(log n) per search

Space complexity: O(1)

Common pitfalls

  • Infinite loop (while l < r vs while l <= r)
  • Forgetting to update both l and r → stuck loop
  • Off-by-one errors when returning (insert pos vs found index)
  • Array must be sorted / condition monotonic
  • Mid calculation safe in Python, but in other languages may need l + (r-l)//2

Binary Search Cheatsheet

Practice problems

Heap

A heap is a specialized binary tree–based data structure that supports efficient retrieval of the min or max element.

  • Min-Heap: Parent ≤ children → root is the smallest.
  • Max-Heap: Parent ≥ children → root is the largest.

Python’s heapq implements a min-heap by default. To simulate a max-heap, push negatives or wrap elements.

1. Priority queue

  • Idea: Always access/remove the element with highest priority (lowest or highest value).
  • When to use: Task scheduling, Dijkstra’s shortest path, A* search, event simulation.
import heapq pq = [] heapq.heappush(pq, (priority, item)) while pq: pr, x = heapq.heappop(pq) # process x with smallest priority

2. Top-K problems

  • Idea: Maintain a heap of size K.
    • Use a min-heap to track largest K elements.
    • Use a max-heap (negated values) to track smallest K elements.
  • When to use: Kth largest element, streaming median, “recommend top N items.”
import heapq pq = [] for x in arr: heapq.heappush(pq, x) if len(pq) > K: heapq.heappop(pq) # pq[0] is Kth largest

3. Heapify/range queries

  • Idea: Convert list → heap in O(n).
    • Useful for repeatedly pulling min/max in sorted order.
  • When to use: Heap sort, scheduling jobs, merging k-sorted lists.
import heapq heapq.heapify(arr) # in-place, O(n) while arr: smallest = heapq.heappop(arr)

Time complexity

  • Push/Pop: O(log n)
  • Heapify: O(n)
  • Peek (min/max): O(1)
  • Building a Top-K heap: O(n log k)

Space complexity: Heap storage: O(n)

Common pitfalls

  • Forgetting max-heap trick: Python only has min-heap → negate values or use PriorityQueue.
  • Memory blowup: Don’t keep all n elements if only k needed.
  • Tuple ordering: heapq compares by first element, then second, etc. Be explicit with priority.
  • Inefficient removal: Removing arbitrary elements is not O(log n). Consider lazy deletion or other DS.

Heap Cheatsheet

Practice problems

Intervals

An interval represents a continuous range, usually expressed as [start, end]. Many problems involve merging, overlapping, or comparing intervals. Interval problems often require sorting + greedy scanning + merging logic.

Intervals are especially common in scheduling, CPU jobs, meeting rooms, calendar events, and range-based computations.

1. Merge intervals

  • Idea: Sort by start time, then merge overlapping ranges into one.
  • When to use: Merging meeting times, collapsing ranges, removing overlaps.
intervals.sort(key=lambda x: x[0]) merged = [] for start, end in intervals: if not merged or merged[-1][1] < start: merged.append([start, end]) else: merged[-1][1] = max(merged[-1][1], end)

2. Interval scheduling (greedy)

  • Idea: Pick the interval with the earliest finishing time that doesn’t conflict with previously chosen ones.
  • When to use: Maximum number of non-overlapping intervals (e.g., meeting scheduling).
intervals.sort(key=lambda x: x[1]) # sort by end count, prev_end = 0, float("-inf") for start, end in intervals: if start >= prev_end: count += 1 prev_end = end

3. Sweep line (Line sweep/events)

  • Idea: Break intervals into events (+1 for start, -1 for end), sort by time, and sweep through.
  • When to use: Maximum overlap, meeting rooms required, busiest time, tracking active intervals.
events = [] for s, e in intervals: events.append((s, 1)) events.append((e, -1)) events.sort() active, max\_active = 0, 0 for \_, delta in events: active += delta max\_active = max(max\_active, active)

Time complexity

  • Sorting dominates: O(n log n)
  • Merging/sweeping: O(n)

Space complexity Storage for merged list or events: O(n)

Common pitfalls

  • Not sorting first: Many interval problems require sorted input.
  • Boundary conditions: Decide whether intervals are inclusive/exclusive ([start, end) vs [start, end]).
  • Greedy missteps: Picking earliest start vs earliest end leads to wrong solutions.
  • Modifying while iterating: Use a new list for merges, don’t overwrite mid-scan.

Intervals Cheatsheet

Practice problems

Next Lesson