Micro-questions over the search module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. The idea
1. Give the dictionary illustration.
Answer
Open a 1,000-page dictionary to page 500, see “M”, and discard pages 1–500 in one step. Open the middle of what remains, see “T”, discard 750–1000. Each flip halves the space.
2. What single property makes that possible?
Answer
The pages are sorted. Shuffle them and you are forced to read every page one by one.
3. Name three production uses.
Answer
Database B-tree index lookups; git bisect, finding the commit that introduced a bug; Python’s bisect module for insertion ranks.
B. The vocabulary
4. What is the search space?
Answer
The range of candidate indices [low, high] that could still hold the target.
5. What is a monotonic function, and why is it here?
Answer
One that only increases or only decreases. It is the precondition for binary search — sortedness is just monotonicity of the array.
C. The algorithm
6. Write iterative binary search.
Answer
low, high = 0, len(arr) - 1
while low <= high:
mid = low + (high - low) // 2
if arr[mid] == target: return mid
elif arr[mid] < target: low = mid + 1
else: high = mid - 1
return -17. Why mid = low + (high - low) // 2 rather than (low + high) // 2?
Answer
Integer overflow. In C/Java/C++, low + high can exceed 2,147,483,647 and wrap negative. Python is immune, but the habit is worth keeping.
8. Why low = mid + 1 and not low = mid?
Answer
arr[mid] has already been tested and rejected. Leaving it in the range means the space may not shrink, which is how infinite loops happen.
9. Costs of linear versus binary search?
Answer
Linear: , space, no precondition. Binary iterative: , space, requires sorted data. Binary recursive: time but call stack.
D. bisect
10. What does bisect_left return?
Answer
The index of the first (leftmost) position where the value could be inserted — i.e. the first occurrence if present. On [1,3,4,4,6,8] with 4, it returns 2.
11. What does bisect_right return?
Answer
The index after all equal values. Same array and value: 4.
12. What does the difference between them give you?
Answer
The count of occurrences — bisect_right(a,v) - bisect_left(a,v).
13. What is insort, and what is its real cost?
Answer
Inserts in place keeping the list sorted. to find the spot but to shift — the search is not the expensive part.
E. Rotated arrays
14. What is the key fact about a rotated sorted array?
Answer
At any split, at least one half — left or right — is guaranteed to be strictly sorted.
15. How do you use that?
Answer
Identify which half is sorted (nums[low] <= nums[mid] means the left is). Then check whether the target lies within that sorted half’s range; if so search it, otherwise search the other.
16. Why can you not simply compare against nums[mid] as usual?
Answer
Because the array is not globally monotonic — a value greater than nums[mid] may still lie to the left of it, across the rotation point.
F. Traps
17. What happens if you binary search an unsorted array?
Answer
No exception is raised. It silently returns incorrect and inconsistent answers.
18. What is the <= versus < loop-bound trap?
Answer
Mixing them up causes infinite loops or skipped boundary elements. while low <= high with mid ± 1 updates is the form that terminates and checks everything.
19. Summarise in one sentence.
Answer
Halve the space on every comparison — , but only on monotonic data, and silently wrong on anything else.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Linear & Binary Search — the module
- Binary Search on the Answer — Question Bank — the generalisation
- Modified Binary Search — the pattern
Software engineering
Infrastructure & security
Computer science
Hardware & engineering