Searching — Chapter Quiz · Data Structures & Algorithms

Question 1

1

Why is mid = Math.floor((lo + hi) / 2) potentially unsafe in languages with fixed-size integers, and what is the safe alternative?

AIt is always safe; no alternative is neededBlo + hi can overflow a 32-bit integer; use mid = lo + Math.floor((hi - lo) / 2) insteadCMath.floor rounds incorrectly; use Math.ceil insteadDDivision is O(n) in some JS engines

In C/Java with 32-bit ints lo + hi overflows when both are large. In JS numbers are 64-bit floats (safe integers up to 2⁵³), so overflow is not a concern, but using lo + ((hi - lo) >> 1) is a canonical pattern worth knowing.

Question 2

2

Binary search on a sorted array has a time complexity of:

AO(n)BO(n log n)CO(log n)DO(1)

Each comparison halves the search space. Starting with n elements, you need at most ⌈log₂n⌉ comparisons — O(log n).

Question 3

3

The 'binary search on the answer' pattern is applicable when:

AThe input array is sortedBThe answer space itself is monotone — feasibility is true for all values beyond some threshold and false before it (or vice versa)CThe array has no duplicate elementsDThe answer is always a prime number

When you can write a canAchieve(x) function that is monotone (all feasible values form a contiguous block), you binary search the answer range rather than an array. Examples: minimum max speed, smallest divisor, koko eating bananas.

Question 4

4

How do you find the pivot index in a sorted-then-rotated array during binary search?

ALinear scan to find the only descending pairBCompare mid to hi: if nums[mid] > nums[hi] the pivot is in the right half; otherwise it is in the left halfCAlways set mid = 0 and scan rightDSort the array first, then apply standard binary search

Comparing nums[mid] to nums[hi] tells you which half is sorted. You then decide which half your target could lie in. The whole search is still O(log n).

Question 5

5

Exponential search is especially useful when:

AThe array is unsortedBThe array is sorted but unbounded or very large, and the target is likely near the beginningCYou need to find all occurrences of a valueDThe array contains only unique integers

Exponential search doubles the probe index (1, 2, 4, 8, …) until it overshoots, then binary searches the found range. For targets near the start it runs in O(log i) where i is the target's index.

Question 6

6

Standard binary search requires the search space to be sorted (or at least monotone with respect to the predicate being tested).

TTrueFFalse

Binary search works only because it can eliminate half the remaining space with each comparison. This is only valid when the ordering (or predicate) is monotone across the space.

Question 7

7

To find the leftmost position at which a value target can be inserted in a sorted array to keep it sorted, you can use a variant of binary search called ___ bound.

Lower bound (or left binary search) finds the first index where arr[i] >= target. Upper bound finds the first index where arr[i] > target. Together they give the range of equal elements.

Question 8

8

Which of the following are real-world applications of binary search? (Select all that apply)

Select all that apply.

ASearching a word in a physical dictionaryBFinding the minimum rate limit that allows all requests to pass in a given time windowCDetermining the square root of n to a desired precisionDBreadth-first traversal of a graph

Dictionaries, threshold problems, and numerical root-finding are classic binary search applications. BFS traversal is a graph algorithm unrelated to binary search.

Test what you learned.