3.6.11 · D5Sorting & Searching
Question bank — Binary search — iterative, recursive; O(log n); searching in sorted - rotated arrays
First, a shared vocabulary so no word below is used before you own it:
True or false — justify
The array [5, 1, 2, 3, 4] can be binary-searched by the plain (non-rotated) algorithm
False — plain binary search needs a globally sorted array; this one has a pivot between 5 and 1, so the "which half" logic can point the wrong way.
Binary search always beats Linear Search on any array
False — on an unsorted array binary search is simply wrong, and on tiny arrays linear search's simplicity can win despite worse Big-O; the win is asymptotic and needs sortedness.
If the array is sorted in descending order, the standard ascending code still finds the target
False — the comparisons
arr[mid] < target assume ascending order; on descending data you must flip the two branches or the algorithm walks away from the target.Doubling the array size adds a constant number of steps, not double
True — steps grow like , and , so each doubling costs just one extra comparison. See Logarithms.
The recursive and iterative versions have the same space cost
False — iterative is extra memory, but recursion stacks up to frames on the call stack.
A rotated sorted array can have both halves around mid unsorted at the same time
False — the pivot is a single location, so it can sit in at most one half; the other half is guaranteed sorted, which is exactly what the algorithm exploits.
while lo <= hi and while lo < hi are interchangeable if you're careful
False — with
< the loop exits while one element (lo == hi) is still untested, so a target equal to that last element is missed.Binary search on a sorted array with duplicates always returns the first occurrence
False — it returns some matching index, whichever
mid lands on; finding the first/last needs the bisect variant.Spot the error
mid = (lo + hi) // 2 — what's wrong and when?
In fixed-width integers (Java/C)
lo+hi can overflow before the division; use lo + (hi-lo)//2, which is equal but never overflows because hi-lo is smaller than either operand.lo = mid when arr[mid] < target — why does this hang?
mid was already compared, so keeping it wastes a slot; when lo == mid the window never shrinks and the loop spins forever. Use lo = mid + 1.hi = mid (no −1) after ruling mid too big — is it fatal?
It can loop forever in the symmetric way: with a 2-element window
mid == lo, setting hi = mid leaves the window unchanged. Use hi = mid - 1.In the rotated code, someone wrote if arr[lo] < arr[mid] (strict). What breaks?
When
lo == mid (a 1-element "left half"), arr[lo] == arr[mid], so strict < misclassifies it as unsorted and the wrong branch runs. The correct guard is arr[lo] <= arr[mid].return mid is missing and the code returns lo when found — always correct?
No — the answer is the matching index
mid, and lo need not equal mid at the moment of the match, so returning lo gives a wrong index.Base case if lo >= hi: return -1 in the recursive version — what's the bug?
lo == hi is a non-empty one-element window that still must be checked; >= throws it away and misses single-element matches. The correct base case is lo > hi.Someone sorts the array inside the search function on every call. What's the real cost mistake?
Sorting is per search, dwarfing the search itself; sort once up front, then run many cheap searches. See Time Complexity & Big-O.
The rotated check uses arr[lo] <= target < arr[mid] but forgets that mid is already handled
That's actually fine — because the equal-to-
mid case is caught earlier by if arr[mid] == target, so excluding arr[mid] from the range with strict < is correct, not a bug.Why questions
Why does halving give and not, say, ?
Because we discard a fixed fraction (half) each step; the count of halvings to reach size 1 solves , i.e. . Discarding a shrinking fraction would give a slower bound. See Recurrence Relations.
Why mid + 1 and mid - 1 rather than symmetric mid, mid?
Because
mid has just been tested and excluded, so it must leave the window; keeping it risks a window that never shrinks (infinite loop).Why does the rotated variant compare arr[lo] to arr[mid] instead of arr[hi]?
To decide which side is sorted: if
arr[lo] <= arr[mid] the left is pivot-free (sorted), otherwise the right is. It picks the half we can reason about with a simple range check.Why is binary search's worst case only one more comparison than its best case for practical sizes?
The tree of possible outcomes has depth ; every path from root to leaf differs by at most one level, so worst and near-best differ by a single step.
Why must the array be sorted, in one sentence about information?
Sortedness is what lets a single comparison at
mid rule out an entire half; without order, one comparison tells you about one element only — that's just Linear Search.Why does a Binary Search Tree give search for the same reason as binary search?
Each node comparison discards one whole subtree (a "half"), so a balanced tree mirrors the halving recurrence .
Why can two different sorted inputs need the same number of comparisons regardless of the target's value?
The step count depends on window size, not on which value we seek; halving proceeds identically until the window is one element, so the bound is either way.
Edge cases
Empty array [], any target — what happens and why?
hi = -1, so lo(0) <= hi(-1) is false immediately; the loop body never runs and it correctly returns −1.Single element [7], searching 7 — does lo <= hi matter?
Yes —
lo == hi == 0, the loop runs once, tests index 0, and finds it; with lo < hi this element would be skipped and 7 reported missing.Target smaller than every element, e.g. find 0 in [3,5,9]
mid keeps landing on values > target, driving hi down until hi < lo; the window empties and it returns −1 — no out-of-bounds access ever occurs.Target larger than every element, e.g. find 99 in [3,5,9]
Symmetrically,
arr[mid] < target drives lo up past hi; window empties, returns −1 safely.A rotated array that wasn't actually rotated, e.g. [1,2,3,4,5] (rotation 0)
arr[lo] <= arr[mid] is always true, so the rotated code degenerates cleanly into ordinary binary search — the pivot-free case is just a rotation of amount 0.Fully rotated so the pivot is at the very start, e.g. [0,1,2,4,5,6,7] searching 0
This is identical to a plain sorted array (rotation wrapped all the way around); the left half is always sorted and it behaves exactly like standard search.
All elements identical, e.g. [2,2,2,2] searching 2 (rotated variant)
arr[lo] == arr[mid] makes the "left sorted" branch fire, but the range test can't distinguish sides when values are equal, so worst case degrades toward — the classic duplicates caveat of rotated search.Two-element window [a, b] — which index does mid pick and does it terminate?
mid = lo + (b-a index gap)//2 rounds down to lo, so it tests the left element first; whichever branch fires shrinks the window to one element, guaranteeing termination.Recall One-line summary of every trap family
Order is mandatory, mid must leave the window, the loop guard must keep the last element alive, the pivot lives in exactly one half, and empty/single/all-equal inputs must each be walked mentally before trusting the code.