Searching looks simple until the constraints become interesting.

If an array contains n elements, a straightforward linear scan takes:

O(n)

But if the data is sorted, structured, or has useful mathematical properties, we can often eliminate large portions of the search space.

That is the central theme of this part:

Don’t search everything. Identify the structure that lets you eliminate candidates.

The Searching section of Elements of Programming Interviews in Python covers first-occurrence search, index-equal-to-value search, cyclically sorted arrays, integer and real square roots, 2D sorted arrays, simultaneous min/max, the k-th largest element, missing IP addresses, and duplicate/missing elements. citeturn0search3turn0search4

1. What Part 11 Is Really Teaching

Don’t approach searching as:

“I need to memorize binary search.”

Instead, think in terms of candidate elimination.

                         SEARCHING
                             |
             +---------------+---------------+
             |               |               |
             v               v               v
        Sorted data     Mathematical     Structured
             |             search            data
             v               |               |
        Binary search        v               v
             |          Square root      2D search
             v
       Boundary search
             |
             +------------------+
             |                  |
             v                  v
       First occurrence      Last occurrence

The fundamental idea is:

Maintain candidate solutions
        ↓
Identify a property that rules out candidates
        ↓
Discard them
        ↓
Repeat

This is why binary search is much more than a lookup algorithm.

2. Linear Search vs Binary Search

Suppose:

A = [2, 5, 8, 12, 17, 21, 30]

A linear search checks:

2
5
8
12
...

Worst case:

O(n)

If the array is sorted, binary search can do much better.

Start with:

left = 0
right = n - 1

Check the middle.

          search space
    +-----------------------+
    |                       |
    |          mid          |
    |           |           |
    +-----------+-----------+

If the target is smaller:

discard right half

If the target is larger:

discard left half

Each comparison removes approximately half the remaining candidates.

Therefore:

Time = O(log n)
Space = O(1)

for an iterative implementation.

3. The Binary Search Invariant

A strong interview answer should not begin with code.

Start with the invariant.

For example:

At every iteration, if the target exists, it must lie within the current search interval [left, right].

Then every update must preserve that statement.

This is the most important mental model for binary search.

Invariant:
target ∈ [left, right], if target exists

After examining mid:

target < A[mid]
        ↓
right = mid - 1

or:

target > A[mid]
        ↓
left = mid + 1

The search space shrinks while the invariant remains true.

4. A Clean Python Binary Search

def binary_search(nums, target):
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid

        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

Complexity:

Time:  O(log n)
Space: O(1)

The expression:

left + (right - left) // 2

is the conventional overflow-safe midpoint calculation in languages with fixed-width integers.

Python integers do not have the same fixed-width overflow behavior, but this form is still clear and conventional.

5. Why Binary Search Is Easy to Get Wrong

The algorithm is conceptually simple.

The boundaries are not.

Common bugs involve:

left < right vs left <= right
whether right = mid or right = mid - 1
whether left = mid can cause an infinite loop
empty arrays
one-element arrays
duplicate values
first/last occurrence
insertion positions

The book emphasizes that binary search has a history of subtle implementation errors. citeturn0search1turn0search6

Staff-level lesson:

The algorithm is not finished when the main case works. The invariant and boundary behavior must also be correct.

6. Search for the First Occurrence

Suppose:

A = [1, 2, 2, 2, 4, 7]

and:

target = 2

A normal binary search may return any occurrence.

But the problem asks for:

first occurrence

The key idea is:

Found target
     |
     v
Don't stop
     |
     v
Can there be another target on the left?
     |
     v
Continue searching left

7. Python — First Occurrence

def first_occurrence(nums, target):
    left, right = 0, len(nums) - 1
    result = -1

    while left <= right:
        mid = left + (right - left) // 2

        if nums[mid] == target:
            result = mid
            right = mid - 1
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return result

Complexity:

Time:  O(log n)
Space: O(1)

The important difference from ordinary binary search is:

result = mid
right = mid - 1

rather than immediately returning.

8. Boundary Search Is a General Pattern

The first-occurrence problem is an example of a broader idea:

Binary search can find a boundary, not just an exact value.

Examples:

first occurrence of x
last occurrence of x
first value >= x
first value > x
last value <= x
first invalid value
first feasible solution

This becomes extremely powerful in optimization problems.

9. Search for the First Value Greater Than a Key

Suppose:

A = [1, 3, 3, 5, 7, 9]

and:

key = 3

We want:

The condition is:

A[i] > key

This is not really a “find value” problem.

It is a:

find first index satisfying condition

problem.

That distinction makes many binary-search problems easier to recognize.

10. Search for an Index Equal to Its Value

Suppose:

A = [-2, 0, 2, 3, 6, 7, 9]

We want:

A[i] == i

Possible answers:

i = 2

because:

A[2] = 2

or:

i = 3

because:

A[3] = 3

A linear scan costs:

O(n)

But the array is:

sorted
distinct

So we can use binary search.

11. The Key Transformation

Define:

f(i) = A[i] - i

Because A is sorted and contains distinct integers:

A[i+1] >= A[i] + 1

therefore:

A[i+1] - (i+1) >= A[i] - i

So:

A[i] - i

is nondecreasing.

That gives us a binary-search property.

At index mid:

A[mid] == mid

→ found.

If:

A[mid] < mid

then:

A[mid] - mid < 0

and we need to move right.

If:

A[mid] > mid

we move left.

This is a beautiful example of transforming a problem into a monotonic condition.

12. Python

def search_entry_equal_to_index(nums):
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if nums[mid] == mid:
            return mid

        if nums[mid] < mid:
            left = mid + 1
        else:
            right = mid - 1

    return -1

Complexity:

Time:  O(log n)
Space: O(1)

13. Cyclically Sorted Arrays

Consider:

[378, 478, 550, 631, 103, 203, 220, 234]

This was originally sorted but rotated.

The smallest element is:

The array has two sorted regions:

[378, 478, 550, 631]
                    \
                     [103, 203, 220, 234]

We want to find the rotation point efficiently.

14. Searching a Rotated Sorted Array

The important observation is:

At least one side of mid remains sorted.

Compare:

nums[mid]

with:

nums[right]

If:

nums[mid] > nums[right]

the minimum must be to the right of mid.

Otherwise:

minimum is at mid or to the left

15. Python — Minimum in a Cyclically Sorted Array

def find_min_rotated(nums):
    left, right = 0, len(nums) - 1

    while left < right:
        mid = left + (right - left) // 2

        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid

    return nums[left]

Complexity:

Time:  O(log n)
Space: O(1)

This assumes the rotated array has distinct elements.

16. Integer Square Root

Suppose:

x = 27

We want:

floor(sqrt(27)) = 5

A naive approach checks:

1²
2²
3²
4²
5²
6²
...

But we can binary-search the answer.

The condition is:

mid² <= x

If true:

mid could be the answer

and we search higher.

If false:

mid is too large

and search lower.

17. Python — Integer Square Root

def integer_sqrt(x):
    if x < 2:
        return x

    left, right = 1, x // 2
    result = 1

    while left <= right:
        mid = left + (right - left) // 2

        if mid * mid <= x:
            result = mid
            left = mid + 1
        else:
            right = mid - 1

    return result

Complexity:

Time:  O(log x)
Space: O(1)

18. Binary Search on the Answer

Integer square root illustrates one of the most reusable search patterns:

We are not searching an array.
We are searching a numerical answer.

The general structure is:

Possible answer range
        ↓
Choose midpoint
        ↓
Check feasibility
        ↓
Eliminate half
        ↓
Repeat

This is commonly called:

binary search on the answer

Examples include:

minimum feasible capacity
maximum possible distance
minimum processing speed
earliest feasible time
largest valid value

The important question is:

Is the feasibility condition monotonic?

If yes, binary search may apply.

19. Real Square Root

For floating-point square roots, we can similarly search over an interval.

For:

x >= 1

the answer lies in:

[1, x]

For:

0 <= x < 1

the answer lies in:

[0, 1]

Then repeatedly test:

mid * mid

and narrow the interval until the desired precision is reached.

20. Python — Real Square Root

def real_sqrt(x, eps=1e-12):
    if x < 0:
        raise ValueError("x must be non-negative")

    if x == 0:
        return 0.0

    left = 0.0
    right = max(1.0, x)

    while right - left > eps:
        mid = left + (right - left) / 2

        if mid * mid <= x:
            left = mid
        else:
            right = mid

    return (left + right) / 2

The number of iterations depends on the requested precision.

This is an important interview distinction:

Integer search:
exact discrete answer

Floating-point search:
approximate answer within tolerance

21. Searching a 2D Sorted Array

Suppose every row and column is sorted:

1   4   7   11
2   5   8   12
3   6   9   16
10  13  14  20

We want to search for:

A naive approach scans every element:

O(rows × columns)

But we can exploit both sorted dimensions.

22. Start at the Top-Right

Start at:

If:

target < current

move left.

Why?

Everything below the current element is even larger.

If:

target > current

move down.

Why?

Everything to the left of the current element is smaller.

So every step eliminates either:

one column

or:

one row

23. Python — 2D Search

def search_matrix(matrix, target):
    if not matrix or not matrix[0]:
        return False

    rows = len(matrix)
    cols = len(matrix[0])

    row = 0
    col = cols - 1

    while row < rows and col >= 0:
        value = matrix[row][col]

        if value == target:
            return True

        if value > target:
            col -= 1
        else:
            row += 1

    return False

Complexity:

Time:  O(rows + cols)
Space: O(1)

The key idea is not the exact starting corner.

It is:

Choose a position from which every comparison lets you eliminate an entire row or column.

24. Find Minimum and Maximum Simultaneously

Suppose we need both:

minimum
maximum

A naive approach finds them independently.

That requires roughly:

2n comparisons

We can do better.

Process elements in pairs.

For every pair:

compare the two values

Then:

smaller → compare with global minimum
larger  → compare with global maximum

This reduces the number of comparisons.

25. Why Pairing Helps

For each pair:

a, b

instead of:

compare a with min
compare a with max
compare b with min
compare b with max

first determine:

small = min(a, b)
large = max(a, b)

Then:

small → minimum candidate
large → maximum candidate

This is an example of reducing redundant comparisons.

Complexity remains:

Time: O(n)
Space: O(1)

but the constant number of comparisons improves.

26. K-th Largest Element

Suppose:

nums = [3, 2, 1, 5, 6, 4]
k = 2

The answer is:

Sorting gives:

[1, 2, 3, 4, 5, 6]

but costs:

O(n log n)

We don’t need the complete ordering.

We only need the element whose rank is:

That leads to selection algorithms.

27. QuickSelect

QuickSelect is related to QuickSort.

Choose a pivot and partition the array:

values < pivot
pivot
values > pivot

If the pivot lands at the desired rank:

done

Otherwise, recurse only into the relevant side.

Unlike QuickSort:

QuickSort
→ process both sides

QuickSelect
→ process only one side

28. Average Complexity of QuickSelect

Expected:

O(n)

Worst case:

O(n²)

The book presents randomized selection as a way to obtain expected linear-time selection. citeturn0search1

This is a critical distinction:

Expected O(n)

does not mean:

Guaranteed O(n)

A Staff-level answer should explicitly state the assumption.

29. Python QuickSelect

One implementation strategy is to work with a target index for the k-th largest element.

import random

def kth_largest(nums, k):
    if not 1 <= k <= len(nums):
        raise ValueError("invalid k")

    target = len(nums) - k
    left, right = 0, len(nums) - 1

    while left <= right:
        pivot_index = random.randint(left, right)
        pivot = nums[pivot_index]

        i = left
        j = right

        while i <= j:
            while nums[i] < pivot:
                i += 1

            while nums[j] > pivot:
                j -= 1

            if i <= j:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
                j -= 1

        if target <= j:
            right = j
        elif target >= i:
            left = i
        else:
            return nums[target]

    return nums[target]

This implementation mutates the input.

For interviews, clarify:

“May I modify the input array?”

If not, make a copy or use another selection strategy.

30. QuickSelect vs Heap

For k-th largest:

QuickSelect

Expected time: O(n)
Space: O(1) auxiliary

when implemented in-place.

Min-heap of size k

Time: O(n log k)
Space: O(k)

Which one should you choose?

Consider the constraints.

Need exact k-th element
        ↓
QuickSelect is attractive

Need streaming input
        ↓
Heap is often more appropriate

Need top k elements
        ↓
Heap is often simpler

Need predictable behavior
        ↓
Consider worst-case guarantees and alternatives

The right algorithm depends on the workload, not just the asymptotic headline.

31. Missing IP Address

The chapter also considers a much larger-scale problem:

Given a collection of IP addresses, find an IP address that does not occur in the collection.

The important issue is the size of the possible address space.

For IPv4:

2^32

possible addresses exist.

A naive solution could store every observed address in a hash set.

That may require substantial memory.

The interesting part of the problem is therefore not simply searching.

It is:

How can we exploit the bounded universe?

32. Bit-Level Thinking for Missing Values

If the universe is known and finite, techniques such as:

bitmaps
partitioning
counting
XOR where applicable

can reduce memory or processing requirements.

However, XOR is only directly suitable for specific missing/duplicate formulations where the mathematical cancellation property applies.

For the missing-IP problem, the key engineering lesson is:

When the universe is bounded, represent membership compactly rather than treating every possible value as an arbitrary object.

33. Duplicate and Missing Elements

Consider an array that should contain:

1, 2, 3, ..., n

but:

one value appears twice
another value is missing

We want both.

A brute-force solution can use a set.

Time: O(n)
Space: O(n)

But there are formulations that exploit arithmetic or XOR properties to reduce auxiliary space.

34. XOR Insight

XOR has two useful properties:

x ^ x = 0

and:

x ^ 0 = x

Therefore, when every expected value appears exactly once except for the missing/duplicate disturbance, XOR can cancel matching values.

For the classic missing-number problem:

expected values
XOR
observed values

leaves the missing value.

For the duplicate-and-missing version, additional reasoning is required to separate the two values.

The important interview lesson is:

Use algebraic cancellation when the input structure provides it.

35. Binary Search as a General Problem-Solving Technique

The most important lesson of this part is broader than sorted arrays.

Binary search works whenever we can identify:

A search space
+
A monotonic decision condition

For example:

Is capacity C sufficient?

may produce:

C too small → False
C large enough → True

So the search space looks like:

False False False False True True True
                      ^
                  boundary

Binary search finds that boundary.

36. The Monotonic Predicate Pattern

Suppose:

def feasible(x):
    ...

and:

feasible(x) = False

for all values below some threshold, then:

feasible(x) = True

for all values above it.

The structure is:

False → False → False → True → True → True

We want the transition point.

That is binary search.

This is one of the most valuable ways to recognize binary-search opportunities in modern coding interviews.

37. Binary Search Decision Tree

When you see a new problem, ask:

Is the data sorted?
       |
      YES
       |
       v
Can I eliminate half after each comparison?
       |
      YES
       |
       v
Binary Search

If the data is not explicitly sorted:

Is there a monotonic property?
       |
      YES
       |
       v
Can I search the answer space?
       |
      YES
       |
       v
Binary Search on Answer

For 2D structures:

Can each comparison eliminate a row/column?
       |
      YES
       |
       v
Structured Search

For selection:

Do I need full ordering?
       |
       NO
       |
       v
Selection / QuickSelect / Heap

38. Common Binary Search Bugs

Bug 1 — Wrong Loop Condition

Mixing:

while left < right:

with updates intended for:

while left <= right:

can skip candidates or create infinite loops.

Bug 2 — Wrong Boundary Update

If mid is known to be too small:

left = mid + 1

If mid may still be a valid answer:

right = mid

instead of:

right = mid - 1

The correct update depends on the invariant.

Bug 3 — Returning Too Early

For first occurrence:

if nums[mid] == target:
    return mid

is wrong.

Instead:

result = mid
right = mid - 1

Bug 4 — Ignoring Duplicates

Many binary-search solutions are correct only when elements are distinct.

Always ask:

Can duplicates exist?

Bug 5 — Forgetting Empty Input

Before coding:

[]

should be considered.

Then:

[only element]

and:

target smaller/larger than every value

39. Searching Complexity Cheat Sheet

Problem	Pattern	Time	Extra Space
Standard binary search	Binary search	`O(log n)`	`O(1)`
First occurrence	Boundary binary search	`O(log n)`	`O(1)`
Entry equal to index	Transformed binary search	`O(log n)`	`O(1)`
Cyclically sorted minimum	Rotated binary search	`O(log n)`	`O(1)`
Integer square root	Binary search on answer	`O(log x)`	`O(1)`
Real square root	Numerical binary search	`O(log(1/ε))` approximately	`O(1)`
2D sorted matrix	Structured elimination	`O(rows + cols)`	`O(1)`
Min + max	Pairwise comparison	`O(n)`	`O(1)`
K-th largest	QuickSelect	Expected `O(n)`	`O(1)` auxiliary
Top K	Heap	`O(n log k)`	`O(k)`

40. Search Pattern Summary

Pattern 1 — Exact Search

Sorted array
    ↓
Binary search

Pattern 2 — First/Last Occurrence

Found target
    ↓
Don't stop
    ↓
Continue toward desired boundary

Pattern 3 — Search a Monotonic Predicate

False False False True True True
                    ^
                 answer

Use binary search.

Pattern 4 — Search a Transformed Property

Example:

A[i] == i

Transform into:

A[i] - i

and exploit monotonicity.

Pattern 5 — Rotated Sorted Data

Two sorted regions
       ↓
Find rotation point
       ↓
Binary search

Pattern 6 — Structured Matrix

Sorted rows + columns
        ↓
Start at informative corner
        ↓
Eliminate row/column

Pattern 7 — Selection

Need rank, not full ordering
        ↓
QuickSelect / Heap

41. What to Practice Until It Becomes Automatic

You should be able to implement and explain:

✓ Standard binary search
✓ First occurrence
✓ Last occurrence
✓ First value >= target
✓ First value > target
✓ Entry equal to its index
✓ Minimum in rotated sorted array
✓ Integer square root
✓ Real square root
✓ Search sorted 2D matrix
✓ Simultaneous min/max
✓ K-th largest using QuickSelect
✓ Missing number
✓ Duplicate + missing number

But the real objective is pattern recognition.

42. Staff-Level Interview Thinking

A junior candidate may hear:

“Search for a number.”

and immediately write a loop.

A Staff candidate should first ask:

Is the input sorted?
Are duplicates possible?
Is the data static or dynamic?
Can preprocessing help?
What is the expected query volume?
Can I eliminate half the candidates?
Is there a monotonic predicate?
Is the answer an element or a boundary?
Do I need the entire ordering?
What are the memory constraints?
Is the data streaming?

These questions often determine the algorithm before the first line of code is written.

43. Search and System Design

Searching patterns also appear in large-scale systems.

For example:

Millions of records
        ↓
Preprocessing / indexing
        ↓
Fast queries

This leads to the broader trade-off:

Preprocessing cost
        ↕
Query latency

For static data, expensive preprocessing can be worthwhile if it dramatically reduces repeated query cost.

For dynamic data, maintaining the index may become expensive.

Therefore, the search problem is not only:

“Which algorithm is fastest?”

It is:

“What workload am I optimizing for?”

44. The Most Important Staff-Level Insight

Binary search is really an elimination strategy.

Linear search says:

Check candidates one by one.

Binary search says:

Prove that half the candidates cannot work.
Discard them.
Repeat.

QuickSelect says:

Prove that one side cannot contain the desired rank.
Discard it.
Repeat.

2D search says:

Prove that an entire row or column cannot contain the answer.
Discard it.
Repeat.

Square-root search says:

Prove that half the numerical answer space is infeasible.
Discard it.
Repeat.

The common pattern is:

Candidate space
      ↓
Structural property
      ↓
Eliminate candidates
      ↓
Smaller candidate space
      ↓
Repeat

That is the deeper idea behind Part 11.

45. Final Interview Cheat Sheet

Sorted array?

Binary search

Need first occurrence?

Binary search + continue left

Need last occurrence?

Binary search + continue right

Need first value satisfying a condition?

Binary search for boundary

Search space isn’t an array but feasibility is monotonic?

Binary search on answer

Rotated sorted array?

Exploit sorted half

Sorted rows + columns?

Start from a corner and eliminate rows/columns

Need k-th largest rather than complete ordering?

QuickSelect or heap

Need minimum and maximum?

Pair elements to reduce comparisons

Missing value from a known universe?

Exploit representation / XOR / bitmap where appropriate

46. Part 11 — Final Takeaway

The deepest lesson from Searching is:

The fastest search is often the one that never examines most of the data.

Before writing a loop, ask:

What structure does the input give me?

Then ask:

What candidates can I eliminate without examining them individually?

That leads to:

Sorted array
    ↓
Binary search

Monotonic predicate
    ↓
Binary search on answer

Rotated sorted array
    ↓
Rotated binary search

Sorted matrix
    ↓
Row/column elimination

Selection problem
    ↓
QuickSelect / Heap

Bounded universe
    ↓
Compact representation

The progression from Part 10 to Part 11 is also important:

Part 10 — Heaps
        ↓
Maintain the best candidate efficiently

Part 11 — Searching
        ↓
Eliminate candidates efficiently

Both are expressions of the same Staff-level principle:

Do not perform work that the problem’s structure allows you to avoid.

Part 11 in the Series

Part 8 — Stacks & Queues
↓
Part 9 — Binary Trees
↓
Part 10 — Heaps
↓
Part 11 — Searching
↓
Part 12 — Hash Tables

The progression now moves from:

Priority
   ↓
Search
   ↓
Constant-time lookup

and prepares the foundation for the next major data-structure pattern: hashing.