Binary Search

The array (or more generally, the search space) must be sorted, or more precisely have a property where you can determine, from any single element, which side of it the target would be on. Without that ordering property, discarding half the search space at each step isn't valid.

Maintain low and high bounds spanning the search space. While low <= high, compute mid = low + (high - low) / 2, compare arr[mid] to the target. If equal, return mid. If arr[mid] < target, the target must be in the right half, so set low = mid + 1. Otherwise set high = mid - 1. If the loop ends without a match, the target isn't present.

(low + high) can overflow in languages with fixed-width integers if both low and high are large, producing an incorrect (wrapped-around) value. low + (high - low) / 2 avoids ever summing two large numbers directly, while computing the same midpoint.

O(log n) time, because each comparison eliminates half of the remaining search space, so it takes about log2(n) steps to narrow down to one element. Iterative implementations use O(1) extra space; recursive implementations use O(log n) space for the call stack, since recursion depth matches the number of halvings.

When you find a match (arr[mid] == target), don't return immediately — record it as a candidate answer, then keep searching the left half by setting high = mid - 1. This keeps narrowing toward the first occurrence rather than stopping at an arbitrary matching index.

It's the mirror image: on a match, record the candidate and continue searching the right half by setting low = mid + 1 instead of narrowing left. Everything else about the loop is the same.

At each step, at least one half relative to mid is guaranteed to still be sorted normally, even though the array as a whole isn't. Check whether the left half (low to mid) is sorted; if so, determine whether the target lies within that range and search there, otherwise search the right half — and symmetrically if the right half is the sorted one instead.

Instead of searching array indices, you binary search over a range of possible answer values, using a feasibility check that is monotonic — once it flips from infeasible to feasible (or vice versa), it doesn't flip back. This applies to problems like "minimum capacity to ship packages within D days," where you binary search over possible capacities rather than searching an array directly.

Binary search's efficiency depends on O(1) access to the middle element at every step. A linked list only supports sequential access, so finding the "middle" from a given pointer takes O(n) traversal — doing this at every step of what should be a logarithmic algorithm erases the benefit entirely, making it no better than a linear scan.

Using while (low < high) when the algorithm's invariants actually require checking the case low == high (or vice versa), causing the search to loop infinitely or terminate one step too early and miss the target. The fix is to be deliberate about the loop invariant — decide up front exactly what low, high, and mid represent, and keep the boundary updates consistent with that invariant.

Binary search over a numeric range (e.g., 0 to x, or 0 to max(1, x)) instead of array indices. At each step, check if mid * mid is close enough to x within your precision tolerance; if mid * mid < x, search the upper half, otherwise search the lower half. This converges in O(log(x / precision)) steps.

As you move through the range of candidate answers in one direction, the feasibility check must consistently switch from false to true (or true to false) exactly once, never flip back. This is what lets binary search safely discard half the candidate range at each step — if the function weren't monotonic, discarding a half could throw away the actual answer.

Compare arr[mid] to arr[mid + 1]. If arr[mid] < arr[mid + 1], a peak must exist somewhere to the right (the sequence is still climbing), so search the right half; otherwise a peak exists to the left or at mid, so search the left half including mid. This works because a peak is guaranteed to exist in the direction the array is still increasing.

Since the matrix is effectively a flattened sorted sequence, you can binary search over a single index from 0 to (rowscols - 1), converting it to a (row, col) pair via division and modulo by the column count, and compare as usual — giving O(log(rowscols)) instead of a full scan.

Track low and high as they converge; when the loop ends, low and high will have crossed such that arr[high] and arr[low] are the two closest surrounding candidates. Compare the target's distance to each and return whichever is closer, handling the boundary cases where one index is out of range.

Each step divides the problem (the search space) roughly in half, discards the half that can't contain the answer, and repeats on the remaining half — the core divide-and-conquer pattern of breaking a problem into a smaller version of itself, without needing to "combine" results afterward since only one half is ever kept.

Functionally they're equivalent, but iterative avoids call-stack overhead and the risk of stack depth issues, and it lets an interviewer directly observe how you manage loop invariants and pointer updates. Recursive versions can look cleaner but hide the same bookkeeping inside call parameters instead of loop variables.

It would consistently search the wrong half at each step — when arr[mid] < target, the algorithm assumes the target is to the right, but in a descending array the target would actually be to the left. It would likely terminate without finding an existing target, or return the wrong result.

Compare arr[mid] to arr[high]. If arr[mid] > arr[high], the minimum must be in the right half (the rotation point is to the right), so set low = mid + 1. Otherwise, the minimum is in the left half including mid, so set high = mid. This narrows to the rotation point, which holds the minimum.

O(n) to build the prefix sum array once, plus O(log n) per query for the binary search, giving O(n + q log n) total — much better than recomputing from scratch for every query.

The core assumption of binary search — that comparing the target to the middle element tells you definitively which half to discard — only holds when the array's ordering guarantees everything before a boundary satisfies one condition and everything after satisfies another. In an unsorted array, the target could be on either side regardless of the comparison, so no half can be safely discarded.

Each comparison halves the remaining search space, so after k comparisons, at most n / 2^k elements remain. Solving for when this shrinks to 1 gives k ≈ log2(n) — for example, an array of ~1,000,000 elements needs only about 20 comparisons in the worst case, versus up to 1,000,000 for linear search.

Binary search over possible capacities, from the maximum single package weight (the theoretical minimum feasible capacity) to the sum of all weights (always feasible in one day's worth of shipping capacity). For each candidate capacity, run a greedy O(n) simulation to check how many days it takes; if it fits within D days, try a smaller capacity, otherwise try a larger one.

An empty array, a single-element array, the target being smaller than every element, the target being larger than every element, and the target matching the first or last element exactly — these boundary conditions are where off-by-one bugs in the loop condition or bound updates tend to surface.

Verifying correctness by manually stepping through a few examples can miss subtle boundary bugs; instead, you define a precise invariant (e.g., "the answer, if it exists, is always within [low, high]") and prove that every loop iteration preserves that invariant. If the invariant holds at the start and is preserved by every update, correctness follows generally rather than just for the examples you happened to trace.