Divide-and-conquer search on sorted data

Intermediate Recursion & structural decomposition

Created by Pavel · 29.04.2026 at 19:04 UTC

Binary search is the textbook logarithmic pattern: each comparison discards half of the remaining candidates. Sorted NumPy arrays, database indexes, and monotonic time series all justify O(log n) lookups where a linear scan would be O(n).

The idea transfers to data science in less obvious places: finding breakpoints in piecewise-constant calibration curves, bisection root-finding for monotone likelihoods, or locating insertion positions for quantile buckets. The invariant is always: the answer lies in one of two halves, and you can decide which half in constant time.

Iterative binary search (two indices, while lo <= hi) avoids recursion depth entirely and is what most engineers ship. Recursive formulations are fine for teaching when n is small.

bisect module (binary search helpers): [1].

Sources

[1]https://docs.python.org/3/library/bisect.html Return to text

University approvals: 0

Tasks

Question 1

Binary search on a sorted array of length n (worst case) uses how many comparison-driven steps, in Big-O notation?

Hint

Halve the search interval each step.

O(1)

O(log n)

O(n)

O(n²)

Question 2

You have a sorted NumPy array of distinct thresholds and a scalar x. You need the index of the largest threshold ≤ x or know that x is below all thresholds. Which pattern fits best?

Hint

Monotone order enables halving.

Always scan the full array—sorting does not help

Shuffle the array each query for fairness

Binary search / bisection on the sorted order

Hash the array into a dict of all prefixes

Question 3

Implement bsearch(sorted_vals, target) returning the index of target or None if absent. sorted_vals is strictly ascending distinct ints. Use one while loop with lo/hi (iterative binary search).

Hint

Invariant: if present, index in [lo, hi].

def bsearch(sorted_vals, target):
    pass

Starter code is prefilled; replace TODO blocks with your solution.

Runtime output (stdout/stderr)

2 test cases will be used for grading

Run checks runtime behavior only. Final correctness is evaluated when you submit.

Card Info

Topic: Recursion & structural decomposition
Difficulty: Intermediate
Completed: 0 users

Creator

Pavel