Binary Search and Efficient Searching Questions

Understanding binary search algorithm, when it's applicable, and ability to implement correctly. Includes recognizing problems that can be solved with binary search on arrays or values.

MediumTechnical

99 practiced

Given a rotated sorted array, compute how many positions it has been rotated (i.e., index of the minimum element) in O(log n) time. Example: [6,7,0,1,2,4,5] -> 2. Implement and explain the invariants used to detect the pivot.

Sample Answer

To find the rotation count (index of minimum) in O(log n) we use a binary search variant that exploits the sorted order except for a single pivot. Key invariant: at any step, the minimum lies in the half where the endpoints are not in sorted order; if subarray is already sorted (nums[left] <= nums[right]) the left is the minimum. We maintain left and right inclusive.

python

def rotation_count(nums):
    """
    Return index of smallest element (number of rotations).
    O(log n) time, O(1) space.
    """
    if not nums:
        return 0  # or raise depending on spec

    left, right = 0, len(nums) - 1

    # If already sorted (no rotation)
    if nums[left] <= nums[right]:
        return left

    while left <= right:
        mid = left + (right - left) // 2
        # Check if mid is pivot (smaller than previous)
        prev = (mid - 1) % len(nums)
        nxt = (mid + 1) % len(nums)
        if nums[mid] <= nums[prev] and nums[mid] <= nums[nxt]:
            return mid

        # Invariant checks:
        # If left..mid is sorted, pivot must be in mid+1..right
        if nums[left] <= nums[mid]:
            left = mid + 1
        else:
            # otherwise pivot is in left..mid-1
            right = mid - 1

    return 0

Key concepts / invariants:- If nums[left] <= nums[right], subarray is fully sorted → minimum at left.- If nums[left] <= nums[mid], left→mid is sorted, so pivot (smaller element) must be in mid+1..right.- Else pivot is in left..mid-1.

Time complexity: O(log n). Space: O(1).

Edge cases:- No rotation (already sorted).- Duplicates require modified logic (>= checks can break invariants).- Single-element or empty arrays.

HardTechnical

100 practiced

You must run a binary search where evaluating the predicate is very expensive (e.g., runs a heavy DB query). Propose strategies to reduce total evaluation cost: caching, memoization, approximation, narrowing bounds cheaply, parallel checks, or early termination. Provide a concrete example and estimate cost improvements.

Sample Answer

Approach: treat predicate evaluation as a costly black box and minimize calls by combining memoization, cheap heuristics to shrink the search range, parallel probing, and early termination when confidence is sufficient.

Concrete plan:- Memoize results keyed by input (and relevant context) so repeated probes or binary-splits reuse answers.- Before a full DB predicate, run a cheap approximate filter (e.g., cached summary table, index lookup, bloom filter) to rule out many inputs quickly.- Use exponential/backoff search to find rough bounds with few cheap checks, then binary search inside bounds.- Parallelize independent probe candidates (when latency matters) and stop outstanding probes once answer determined.- Early-stop with statistical confidence: if predicate is monotonic but noisy, sample neighbors and accept answer when probability > threshold.

Example:Goal: find maximum commit timestamp t s.t. heavyPredicate(t) true. Heavy call ≈ 500ms; cheap index check ≈ 5ms.1) Exponential search using cheap-index to find [low,high] in ~logK cheap checks (cost 5ms * logK).2) Binary search inside bounds. For each mid: - Check memo; if miss, run cheap-index; only if cheap-index ambiguous, run heavyPredicate.3) Parallelize two mids when acceptable; cancel remaining queries when result decided.

Cost estimate (1000-element range, no cache):- Pure binary: ~10 heavy calls = 10 * 500ms = 5s.With strategy:- Exponential cheap: ~10 * 5ms = 50ms.- Binary cheap checks: ~10 * 5ms = 50ms.- Heavy calls only on ambiguous mids, suppose 2 heavy calls = 1s.Total ≈ 1.1s — ~4.5x improvement. With memoization across runs (cache hit rate 50%) heavy calls drop further; expect 8–10x effective savings.

Trade-offs and considerations:- Maintain cache invalidation when underlying data changes.- Cheap approximations can false-positive/negative; tune thresholds.- Parallelization increases resource use and complexity; measure cost vs. latency gains.- If strict correctness required, avoid approximations that can change monotonicity.

This combination minimizes wall-clock latency and total expensive evaluations while preserving correctness and allowing configurable accuracy/latency trade-offs.

EasyTechnical

99 practiced

Before using binary search, a caller wants to ensure the array is sorted. Describe an efficient approach to verify sortedness for a single check and discuss trade-offs for one-time versus repeated searches. If the array is not sorted and you must support many queries, what strategies would you recommend?

Sample Answer

To verify an array is sorted for a single binary-search precondition, the cheapest correct check is a single linear scan: confirm every element <= next element (for non-decreasing). That’s O(n) time, O(1) extra space.

Example (Python):

python

def is_sorted(arr):
    # returns True if arr is non-decreasing
    for i in range(len(arr) - 1):
        if arr[i] > arr[i+1]:
            return False
    return True

Why this approach:- It’s optimal for a single check because you must potentially inspect each element to prove global sortedness.- Time: O(n). Space: O(1).

Trade-offs — one-time vs repeated searches:- One-time: If you only need to run binary search once, doing an O(n) sortedness check then binary search (O(log n)) costs O(n) overall — often acceptable.- Repeated queries: Repeating O(n) checks before each binary search is wasteful (O(q·n)). Better to pay an upfront cost to enable fast queries.

Strategies when array is unsorted but many queries required:1. Sort once: sort the array (O(n log n)) and run binary searches in O(log n) each. Best when q is large: total O(n log n + q log n).2. Maintain a sorted copy / index: keep original for writes but maintain a sorted auxiliary structure (balanced BST, skip list, or sorted list) to answer membership/range queries quickly while allowing controlled updates.3. Incremental / lazy sorting: on first query, sort and mark sorted; subsequent queries are fast.4. For dynamic data with frequent inserts/deletes: use a balanced tree (e.g., std::set, TreeMap) or order-statistics tree / Fenwick for rank queries.5. Caching results for repeated identical queries or using hashing for membership (O(1) average) if order not required.

Pick based on q, frequency of updates, memory budget, and required operations (membership vs rank vs nearest neighbor).

EasyTechnical

99 practiced

Explain the difference between lower_bound and upper_bound on a sorted array. Define each precisely (in terms of first index >= target and first index > target), show how to compute the count of a value using them, and give a short example: nums=[1,2,2,2,3], target=2.

MediumTechnical

72 practiced

You have time-stamped monitoring metric logs that are monotonic for a given window. Design an algorithm to find the first timestamp when the metric exceeds a threshold using binary search across daily partitions and a secondary binary search within a day. Discuss trade-offs when logs are partitioned across multiple storage tiers.

Sample Answer

Approach: do a two-level binary search—first across daily partitions to find the earliest day where the monotonic metric can exceed the threshold, then within that day do a binary search on timestamps. This minimizes expensive scans and accessor calls.

Python-style pseudocode:

python

def find_first_exceed(partitions, threshold, read_day_range, read_timestamp):
    # partitions: list of day identifiers sorted ascending
    # read_day_range(day) -> (min_val, max_val) for that day (cheap metadata)
    # read_timestamp(day, ts) -> value at timestamp (costly)
    lo, hi = 0, len(partitions)-1
    candidate_day = None

    # Binary search across days using per-day min/max
    while lo <= hi:
        mid = (lo+hi)//2
        dmin, dmax = read_day_range(partitions[mid])
        if dmax <= threshold:
            lo = mid + 1
        else:
            candidate_day = mid
            hi = mid - 1

    if candidate_day is None:
        return None

    # Binary search within day assuming monotonic across timestamps
    day = partitions[candidate_day]
    start_ts, end_ts = day.start_ts, day.end_ts
    lo, hi = start_ts, end_ts
    ans = None
    while lo <= hi:
        mid = (lo+hi)//2
        val = read_timestamp(day, mid)
        if val <= threshold:
            lo = mid + 1
        else:
            ans = mid
            hi = mid - 1
    return (day, ans)

Key points:- Use cheap per-day summaries (min/max, or bloom/time-index) to avoid reading full days.- Secondary search is exact and reads only O(log T) timestamps.

Complexity:- Day-level: O(log D) metadata reads.- In-day: O(log N_day) timestamp reads.- Total reads dominated by expensive timestamp reads ~O(log D + log N_day).

Trade-offs with storage tiers:- Hot tier: random timestamp reads cheap -> fine.- Cold tier (archival): random reads expensive or batched; prefer coarser day-level decisions and, if needed, fetch the day as a contiguous block and binary-search in-memory.- If metadata missing, you may need to probe endpoints; add caching of day min/max.- For high write/ingest windows, ensure summaries are updated atomically; tolerate small staleness if acceptable.

Edge cases:- Non-monotonic noise within day — require monotonic guarantee or pre-aggregation.- Sparse timestamps — adjust binary steps to nearest existing record.- Threshold never exceeded or exceeded at first sample.

Unlock Full Question Bank

Get access to hundreds of Binary Search and Efficient Searching interview questions and detailed answers.

Join thousands of developers preparing for their dream job.