Binary Search and Divide And Conquer Questions

Covers binary search algorithms and the divide and conquer problem solving paradigm. Candidates should know the classic binary search on sorted arrays, off by one and loop invariant considerations, iterative and recursive implementations, and common variants such as searching in rotated sorted arrays, finding first or last occurrence, and search in ranges. Include advanced variants like search on monotonic functions and binary search on answer. Cover divide and conquer design patterns including problem partitioning, conquering subproblems, and combining results with attention to recurrence relations and time complexity analysis. Emphasize edge cases, correctness proofs, complexity trade offs in time and space, and practical considerations for constrained or real time systems such as memory partitioning and latency constraints. Questioners may probe algorithm invariants, complexity derivations, and application of divide and conquer to design efficient solutions.

HardTechnical

54 practiced

Explain divide-and-conquer DP optimization (also called monotone or divide-and-conquer optimization) that can reduce DP from O(n^2) to O(n log n) or O(n). State the prerequisites (monotone argmin or quadrangle inequality), derive how to restrict search ranges when computing dp[l..r] from previous opt ranges, and provide a code sketch that demonstrates the technique and its complexity analysis.

Sample Answer

Divide-and-conquer DP optimization speeds up DP of the formdp[i] = min_{k < i} { dp_prev[k] + C(k, i) }when the argmin index for dp entries is monotone: opt[i] ≤ opt[i+1]. Two common sufficient conditions:- Monotone argmin (explicitly holds), or- Quadrangle inequality / Knuth-Yao conditions: C(a,c)+C(b,d) ≤ C(a,d)+C(b,c) for a ≤ b ≤ c ≤ d, which implies monotone opt.

Idea and derivation:Compute dp for a range of i (say l..r) recursively. If we know opt indices for the boundaries or from previous layer, we can prove opt[i] lies in [opt_l, opt_r]. Use divide-and-conquer: compute mid=(l+r)/2, find best k in [opt_l,opt_r] by brute force (O(opt_r-opt_l+1)). Recurse left with [l,mid-1] and opt range [opt_l,opt_mid], and right with [mid+1,r] and opt range [opt_mid,opt_r]. Because opt ranges shrink overall work becomes O(n log n) if each level scans O(n) total, or O(n) if additional structure reduces scans.

Code sketch (C++):

cpp

using ll = long long;
const ll INF = 9e18;
vector<ll> dp_prev, dp;
ll cost(int k,int i); // implement C(k,i)

void solve_range(int L,int R,int optL,int optR){
  if(L>R) return;
  int mid = (L+R)>>1;
  pair<ll,int> best={INF,-1};
  for(int k=optL;k<=min(optR,mid-1);++k){
    best = min(best, {dp_prev[k]+cost(k,mid), k});
  }
  dp[mid]=best.first;
  int optMid=best.second;
  solve_range(L,mid-1,optL,optMid);
  solve_range(mid+1,R,optMid,optR);
}

void compute_dp_layer(int n){
  dp.assign(n+1,INF);
  solve_range(1,n,0,n);
}

Complexity:Each layer of recursion does O(number of candidate k checked). Under monotone opt, total checks per dp layer is O(n log n) worst (often O(n) with careful amortization); overall O(n log n) per layer or O(n) if aggregate checks are O(n). Space O(n). Edge cases: ensure cost is defined and satisfies prerequisites, 0-based vs 1-based indices, handle ties deterministically.

EasyTechnical

95 practiced

Implement lower_bound in C++: given a sorted vector<int> arr and int target, return the lowest index in [0,n] where target can be inserted to keep arr sorted. Examples: arr=[1,3,3,5], target=3 -> 1; target=4 -> 3. Provide iterative code using binary search, ensure O(log n) time, and discuss relationship to std::lower_bound and off-by-one guarantees.

Sample Answer

Approach: use an iterative binary search that maintains a half-open search interval [l, r) or closed interval [l, r]. Here I use [l, r) so the loop invariant is that the answer lies in [l, r). That yields clean off-by-one guarantees and returns n when target is greater than all elements. This is equivalent to std::lower_bound (returns first position where *it >= target).

cpp

#include <vector>

int lower_bound_index(const std::vector<int>& arr, int target) {
    int n = arr.size();
    int l = 0, r = n; // search space: [l, r)
    while (l < r) {
        int mid = l + (r - l) / 2;       // avoids overflow
        if (arr[mid] < target) {
            l = mid + 1;                // answer is in (mid, r)
        } else {
            r = mid;                    // answer is in [l, mid]
        }
    }
    return l; // l == r and is the insertion index in [0, n]
}

Key points:- Time: O(log n), Space: O(1).- Off-by-one: using [l, r) and updating r=mid or l=mid+1 avoids infinite loops and ensures termination.- Relationship to std::lower_bound: returns the same index as std::lower_bound(arr.begin(), arr.end(), target) - arr.begin().Edge cases:- Empty array returns 0.- All elements < target returns n.- All elements >= target returns 0.- Duplicates: returns index of first element >= target.

MediumTechnical

60 practiced

Describe the divide-and-conquer approach to count inversions in an array by modifying merge sort. Provide pseudocode that returns a 64-bit inversion count and derive the recurrence T(n)=2T(n/2)+Θ(n). Solve the recurrence to Θ(n log n) and explain how to handle equal elements so you don't overcount inversions.

Sample Answer

Approach (high level):Use divide-and-conquer: recursively count inversions in left and right halves, then count cross-inversions during merge. When merging two sorted halves, every time an element from the right half is placed before remaining elements in the left half, those remaining left elements each form an inversion with that right element. Use a 64-bit accumulator to avoid overflow.

Pseudocode (returns 64-bit count):

python

# Python-like pseudocode; use int64 for count
def sort_count(arr, lo, hi):
    # sorts arr[lo:hi] in-place and returns inversion count (int64)
    if hi - lo <= 1:
        return 0  # no inversions
    mid = (lo + hi) // 2
    inv = sort_count(arr, lo, mid)
    inv += sort_count(arr, mid, hi)
    # merge step counting cross inversions
    temp = []
    i, j = lo, mid
    while i < mid and j < hi:
        if arr[i] <= arr[j]:
            # important: use <= so equal elements are taken from left first
            temp.append(arr[i])
            i += 1
        else:
            # arr[i] > arr[j]: all remaining left elements [i..mid-1] invert with arr[j]
            temp.append(arr[j])
            inv += int64(mid - i)  # add count of inversions
            j += 1
    # append leftovers
    while i < mid:
        temp.append(arr[i]); i += 1
    while j < hi:
        temp.append(arr[j]); j += 1
    # copy back
    arr[lo:hi] = temp
    return inv

# caller:
# count = sort_count(arr, 0, len(arr))

Why use arr[i] <= arr[j] for equality:If arr[i] == arr[j], picking the left element first (<=) ensures we do NOT count it as an inversion (inversions require strict >). If we instead placed right elements before equal left elements, we'd overcount. This keeps merge stable and correct.

Recurrence and solution:T(n) = 2 T(n/2) + Θ(n) because we recursively solve two halves of size n/2 and do linear-time merging. By Master Theorem, a = 2, b = 2 => n^{log_b a} = n. Case 2 gives T(n) = Θ(n log n).

Edge cases:- Use 64-bit integer (int64) for inv to handle up to n(n-1)/2 for large n.- Works with duplicates due to <= tie-breaker.

HardTechnical

61 practiced

Design a divide-and-conquer algorithm for the maximum subarray (maximum contiguous sum). Provide pseudocode for divide, conquer, and combine steps (left max, right max, crossing max), prove correctness, solve the recurrence T(n)=2T(n/2)+Θ(n) to get Θ(n log n), and compare to Kadane's O(n) algorithm. Discuss when divide-and-conquer could be preferred (e.g., parallelism).

Sample Answer

Approach (brief): Use divide-and-conquer. Split array A into left and right halves, recursively compute max subarray for each half, and compute max subarray crossing the midpoint (max suffix of left + max prefix of right). Return max of three.

Pseudocode:

python

def max_subarray(A, lo, hi):  # inclusive lo, exclusive hi
    if hi - lo == 1:
        return A[lo]
    mid = (lo + hi) // 2
    left_max = max_subarray(A, lo, mid)
    right_max = max_subarray(A, mid, hi)
    # crossing max: max suffix of left + max prefix of right
    left_suffix = -inf
    s = 0
    for i in range(mid-1, lo-1, -1):
        s += A[i]; left_suffix = max(left_suffix, s)
    right_prefix = -inf
    s = 0
    for i in range(mid, hi):
        s += A[i]; right_prefix = max(right_prefix, s)
    cross_max = left_suffix + right_prefix
    return max(left_max, right_max, cross_max)

Correctness sketch:- Base case trivial for single element.- Inductive step: any max contiguous subarray either lies entirely left, entirely right, or crosses mid. Recursion finds left_max and right_max; explicit scan finds best crossing subarray. Therefore algorithm returns optimal.

Recurrence and solution:T(n) = 2T(n/2) + Θ(n) (two recursive halves + linear work computing crossing sums).By Master Theorem, a = 2, b = 2, f(n) = Θ(n) => f(n) = Θ(n^{log_b a}) = Θ(n). So T(n) = Θ(n log n).

Comparison to Kadane:- Kadane’s dynamic programming runs in O(n) time and O(1) space: iterate and keep current_max, global_max. It is simpler and strictly faster asymptotically and practically for single-threaded runs.- Divide-and-conquer: O(n log n) sequentially, but exposes parallelism—left and right recursions are independent and can be executed in parallel, yielding O(n) work but O(log n) span (parallel time) if combined appropriately. Also useful when working with external memory or divide-only paradigms, or when you already partition data across nodes.

When to prefer divide-and-conquer:- Parallel/distributed environment where halves can be processed concurrently.- Educational/contextual reasons (demonstrate recurrence reasoning).- When array is immutable and you want simple divide-based partitioning across workers with low communication (only crossing sums need passing).- For debugging correctness with clear structural proof.

Edge cases:- All negative numbers (algorithm returns max single element).- Empty array (define behavior: maybe -inf or 0 depending on spec).

HardTechnical

57 practiced

Given a huge read-only sorted dataset on disk (too large for RAM), design and provide pseudocode for an external-memory binary search that minimizes disk seeks and memory footprint. Take block size B into account, explain how to align probes to block boundaries, describe prefetching and caching policies for block reads, and analyze I/O complexity in terms of number of block reads and seeks.

Sample Answer

Approach: Do binary search at block granularity. Treat disk as sequence of fixed-size blocks (B bytes / records). Each probe reads one block containing the midpoint record; compute mid index, map to block number floor(mid / records_per_block), read that block (aligned), inspect record, and adjust low/high. Use an LRU block cache of small capacity C blocks and asynchronous prefetch of neighboring blocks when a probe jumps near them to amortize seeks.

Pseudocode (Python-like):

python

# Assume: N records, R = records_per_block, B = block size in bytes
def external_binary_search(target):
    low, high = 0, N - 1
    cache = LRUCache(capacity=C)           # holds blocks
    while low <= high:
        mid = (low + high) // 2
        block_id = mid // R
        block = read_block(block_id, cache)   # aligned read
        rec = block[mid % R]
        if rec == target: return True
        if rec < target: low = mid + 1
        else: high = mid - 1
        # Proactive prefetch: when jump distance > 1 block, prefetch neighbor
        prefetch_candidates = prefetch_plan(low, high, R)
        for b in prefetch_candidates:
            async_prefetch(b, cache)
    return False

def read_block(id, cache):
    if cache.contains(id): return cache.get(id)
    data = disk_read_block_aligned(id)   # single seek + read
    cache.put(id, data)
    return data

Key points:- Align probes: compute block_id = floor(index / R); always read full block to avoid extra seeks.- Minimize seeks: binary search touches O(log(N/R)) distinct block IDs (not log N), since many index steps stay within same block.- Prefetching: when probe moves toward a range, async prefetch adjacent block(s) in that direction (1–2 blocks) to overlap seek time.- Caching: small LRU or CLOCK cache of C blocks; keep recently accessed blocks (midpoints) — choose C = O(log(N/R)) to retain previously probed blocks.I/O complexity:- Block reads = O(log(N/R)) worst-case block reads.- Disk seeks ≈ O(log(N/R)) seeks; prefetching can convert some seeks into sequential reads if accesses are to contiguous blocks, but random midpoints still require seeks.Trade-offs:- Larger R reduces number of probes but increases wasted bandwidth per read.- Prefetch too aggressively wastes I/O; tune prefetch depth by observed access pattern.

Unlock Full Question Bank

Get access to hundreds of Binary Search and Divide And Conquer interview questions and detailed answers.

Join thousands of developers preparing for their dream job.