Binary Search: Intermediate

The search space is not always an array. Sometimes it is a range of answers.

The search space is not always an array. Sometimes it is a range of answers.

Category

Python

Difficulty

intermediate

Duration

30 minutes

Challenges

0 hands-on challenges

Topics covered: Binary Search on the Answer, Find Peak Element, Median of Two Sorted Arrays, bisect with Custom Keys, DE Applications: Intermediate

Lesson Sections

1. Binary Search on the Answer (concepts: pyBinarySearchAnswer, pyFeasibilityFunction)

   This is the most important intermediate binary search concept. The insight: instead of searching for a value in an array, you binary search on the range of possible answer values. You define a feasibility function is_feasible(x) that returns True if answer x is achievable and False if it is not. The function must be monotonic: if x is feasible, then everything easier than x is also feasible. Binary search finds the minimum x such that is_feasible(x) is True. Template: Binary Search on the Answer

2. Find Peak Element (concepts: pyPeakElement, pyDirectionalBinarySearch)

   LeetCode 162. Find Peak Element. A peak is any element strictly greater than its neighbors. The array may not be sorted. Binary search should not work on an unsorted array -- or so the candidate thinks. The insight that makes this problem click is that binary search does not require global sortedness. It only requires that you can determine which half of the current search space contains an answer. And for peak finding, you can. The Key Insight Compare nums[mid] with nums[mid+1]. If nums[mid] <

3. Median of Two Sorted Arrays (concepts: pyMedianSortedArrays, pyPartitionBinarySearch)

   LeetCode 4. Median of Two Sorted Arrays. O(log(min(m,n))). This is widely considered the hardest standard binary search problem and appears at Google, Meta, and Stripe senior-level interviews. Most candidates either cannot solve it at all, or solve it in O(m+n) by merging the arrays (naive) and get partial credit. The O(log) solution requires a deeper insight, and the interview credit for explaining it clearly -- even if you do not get the code perfect -- is enormous. The Insight: Binary Search

4. bisect with Custom Keys (concepts: pyBisectCustomKey, pySortedList)

   Python's bisect module works on values, not keys. If your sorted list contains tuples, objects, or anything where you want to binary search on a transformed value, you need to know the workarounds. Python 3.10 added a key parameter to bisect_left and bisect_right. For older versions, you have two options: extract a parallel list of keys, or use the SortedList from the sortedcontainers library. Both approaches come up in production code and occasionally in interviews. Python 3.10+: The key Parame

5. DE Applications: Intermediate (concepts: pyBinarySearchPartition, pyLogThreshold, pyBtreeSearch)

   The intermediate binary search patterns map directly onto the kinds of problems data engineers deal with at scale. Range partitioning is a binary search on the answer (where should this row go?). Threshold detection in logs is a first-occurrence binary search. B-tree lookups are binary search on sorted pages. Knowing this is not just a fun fact -- it is the kind of system-level connection that gets you points in system design rounds. Range Partitioning: Binary Search for the Right Bucket Hive, B