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 -1

7. 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

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to Searching