A beginner-friendly, humorous, and practical guide to binary search, its time complexity, Python implementation, common variations, interview patterns, and real AI engineering use cases.

---

😂 Imagine Searching for One File in a Very Organised Office

Suppose your manager asks:

“Please find invoice number 7,642.”

You open a cabinet containing 10,000 invoices.

There are two possible approaches.

Approach 1: Linear Search

Start from invoice number 1.

Then 2....Then 3....Then 4......... then

After several hours, two coffees, and one career rethink, you finally reach 7,642.

Approach 2: Binary Search

Open the cabinet near the middle.

You see invoice 5,000.

Since 7,642 is larger, ignore everything before 5,000.

Open the middle of the remaining section.

You see 7,500.

Still too small.

Ignore the lower half again.

Continue until only one answer remains.

That is binary search.

Binary search does not search faster by running more aggressively.

It searches faster by repeatedly throwing away half of the remaining possibilities.

In other words:

Binary search is the algorithmic version of refusing to check places where the answer cannot possibly be.

A very healthy boundary-setting technique. 😄

---

🤖 Why Binary Search Still Matters in the Age of AI

AI systems may look magical from the outside:

Prompt → Model → Intelligent Answer

But underneath, they still depend on ordinary engineering problems:

• Finding thresholds

• Searching sorted logs

• Locating token boundaries

• Choosing the largest safe batch size

• Looking up timestamps

• Finding insertion positions

• Selecting model configurations

• Searching a monotonic answer space

• Identifying the first valid or last valid option

Binary search appears whenever:

1. The data is sorted, or

2. The answer space behaves monotonically

A monotonic condition means that once something becomes true, it stays true—or once it becomes false, it stays false.

Example:

Batch size:  1  2  4  8  16  32  64
Fits GPU?:   Y  Y  Y  Y   Y   N   N

Once the batch stops fitting, larger batches will usually not fit either.

That creates a searchable boundary.

Binary search can find the largest safe batch size without testing every possible value.

This pattern is extremely useful in AI engineering.

---

📚 The One Requirement Everyone Forgets

Binary search requires the search space to be ordered.

For a normal list search, the values must be sorted.

Correct:

values = [2, 5, 8, 12, 19, 31, 44]

Incorrect:

values = [19, 2, 44, 8, 31, 5, 12]

Trying binary search on unsorted data is like using a dictionary whose pages were shuffled.

The algorithm is not slow.

The information it relies on has been destroyed.

---

🧠 The Core Idea

Take a sorted list:

values = [3, 8, 12, 17, 24, 31, 46]

Search for:

target = 31

Start with three positions:

left   = beginning
right  = end
middle = halfway point

Check the middle value.

• If it equals the target, return it

• If the target is smaller, search the left half

• If the target is larger, search the right half

Repeat until:

• The target is found, or

• The search range becomes empty

---

🎬 Binary Search Step by Step

Search for 31:

flowchart TD
    A["Sorted values: 3, 8, 12, 17, 24, 31, 46"] --> B["Middle value = 17"]
    B --> C{"Is 31 equal to 17?"}
    C -->|"No, 31 is larger"| D["Discard left half including 17"]
    D --> E["Remaining: 24, 31, 46"]
    E --> F["Middle value = 31"]
    F --> G["Target found"]

The key operation is elimination.

After every comparison, approximately half the remaining search space disappears.

Very efficient.

Very dramatic.

Half the candidates are removed from the meeting without being allowed to speak.

---

🛠️ Iterative Binary Search in Python

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

    while left <= right:
        middle = left + (right - left) // 2
        middle_value = values[middle]

        if middle_value == target:
            return middle

        if target < middle_value:
            right = middle - 1
        else:
            left = middle + 1

    return -1

Usage:

values = [3, 8, 12, 17, 24, 31, 46]

position = binary_search(values, 31)

print(position)

Output:

5

When the value does not exist:

print(binary_search(values, 99))

Output:

-1

---

🔍 Understanding Every Variable

left

The first index still included in the search.

right

The final index still included in the search.

middle

The index halfway between left and right.

middle = left + (right - left) // 2

You may also see:

middle = (left + right) // 2

Both work in Python.

The first form is commonly preferred across languages because it avoids integer overflow in languages with fixed-width integers.

Python integers do not overflow in the same way, but learning the safer pattern is still useful.

---

🚪 Why the Loop Uses left <= right

while left <= right:

When left == right, one candidate remains.

That final candidate still needs to be checked.

Using:

while left < right:

without carefully changing the rest of the logic may skip the final possible answer.

Binary search is full of tiny boundary decisions.

The algorithm is short.

The off-by-one bugs are highly experienced.

---

📊 Time Complexity

Binary search repeatedly halves the input.

n
n / 2
n / 4
n / 8
...
1

The number of halvings is approximately:

log₂(n)

Therefore:

Time complexity: O(log n)

Number of values	Maximum comparisons, approximately
8	3
16	4
1,024	10
1,000,000	About 20
1,000,000,000	About 30

A linear search through one billion values may inspect one billion items.

Binary search needs roughly thirty comparisons.

Thirty.

That is not an optimisation.

That is an entirely different lifestyle.

---

💾 Space Complexity

The iterative version uses a few variables:

left, right, middle

Extra space:

O(1)

---

🔁 Recursive Binary Search

def binary_search_recursive(
    values,
    target,
    left,
    right
):
    if left > right:
        return -1

    middle = left + (right - left) // 2
    middle_value = values[middle]

    if middle_value == target:
        return middle

    if target < middle_value:
        return binary_search_recursive(
            values,
            target,
            left,
            middle - 1
        )

    return binary_search_recursive(
        values,
        target,
        middle + 1,
        right
    )

Usage:

values = [3, 8, 12, 17, 24, 31, 46]

position = binary_search_recursive(
    values,
    24,
    0,
    len(values) - 1
)

print(position)

Time:

O(log n)

Call-stack space:

O(log n)

The recursive version is elegant.

The iterative version is usually simpler and more memory-efficient.

Recursion says:

“Let future me solve the smaller problem.”

The call stack quietly keeps the receipts.

---

🆚 Linear Search vs Binary Search

Feature	Linear Search	Binary Search
Requires sorted data	No	Yes
Best-case time	O(1)	O(1)
Average time	O(n)	O(log n)
Worst-case time	O(n)	O(log n)
Random access preferred	No	Yes
Good for tiny data	Excellent	Sometimes unnecessary
Good for massive sorted data	Poor	Excellent

Binary search is not always automatically better.

If data is unsorted and searched only once, sorting may cost:

O(n log n)

A single linear scan may be cheaper.

If the same data is searched thousands of times, sorting once and using binary search repeatedly may be worthwhile.

The right algorithm depends on the complete workload.

---

⚠️ Binary Search and Linked Lists

Can binary search be used on a linked list?

Technically, yes.

Practically, it is usually a poor match.

Binary search needs fast access to the middle element.

Arrays provide:

O(1)

indexed access.

Linked lists require:

O(n)

time to walk to the middle.

Repeatedly finding middle nodes destroys the usual performance advantage.

Binary search loves arrays.

Linked lists respond:

“I can find the middle, but first let me walk there.”

---

🔂 Binary Search with Duplicate Values

Consider:

values = [2, 4, 4, 4, 7, 9, 12]

A normal binary search for 4 may return any matching position:

1, 2, or 3

That is not incorrect.

It found the target.

But real systems often need more precise answers:

• First occurrence

• Last occurrence

• Total count

• First value greater than or equal to the target

• First value strictly greater than the target

These are boundary-search problems.

---

⬅️ Find the First Occurrence

When the target is found, do not stop immediately.

Save the answer and continue searching left.

def find_first(values, target):
    left = 0
    right = len(values) - 1
    answer = -1

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

        if values[middle] == target:
            answer = middle
            right = middle - 1
        elif values[middle] < target:
            left = middle + 1
        else:
            right = middle - 1

    return answer

Usage:

values = [2, 4, 4, 4, 7, 9, 12]

print(find_first(values, 4))

Output:

1

Time:

O(log n)

---

➡️ Find the Last Occurrence

When the target is found, continue searching right.

def find_last(values, target):
    left = 0
    right = len(values) - 1
    answer = -1

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

        if values[middle] == target:
            answer = middle
            left = middle + 1
        elif values[middle] < target:
            left = middle + 1
        else:
            right = middle - 1

    return answer

Usage:

print(find_last(values, 4))

Output:

3

---

🔢 Count Occurrences

def count_occurrences(values, target):
    first = find_first(values, target)

    if first == -1:
        return 0

    last = find_last(values, target)

    return last - first + 1

Usage:

print(count_occurrences(values, 4))

Output:

3

Complexity:

O(log n)

Two binary searches are still O(log n).

Big O ignores constant multipliers.

Two very fast searches remain very fast.

---

📍 Find the Insertion Position

Suppose we have:

scores = [10, 20, 30, 40, 50]

Where should 35 be inserted to preserve sorting?

Answer:

Index 3

def insertion_position(values, target):
    left = 0
    right = len(values)

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

        if values[middle] < target:
            left = middle + 1
        else:
            right = middle

    return left

Usage:

print(insertion_position(scores, 35))

Output:

3

This pattern is often called lower bound.

It finds the first position whose value is greater than or equal to the target.

---

⬆️ Lower Bound and Upper Bound

Lower bound

The first index where:

value >= target

Upper bound

The first index where:

value > target

def upper_bound(values, target):
    left = 0
    right = len(values)

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

        if values[middle] <= target:
            left = middle + 1
        else:
            right = middle

    return left

With:

values = [2, 4, 4, 4, 7, 9]

For target 4:

lower bound = 1
upper bound = 4

The count is:

upper_bound(values, 4) - insertion_position(values, 4)

Output:

3

These two patterns appear frequently in:

• Databases

• Ranking systems

• Sorted event logs

• Range queries

• Threshold selection

• Interview questions

---

🐍 Python's Built-In bisect Module

Python already provides efficient insertion-point searches.

from bisect import bisect_left, bisect_right

values = [2, 4, 4, 4, 7, 9]

print(bisect_left(values, 4))
print(bisect_right(values, 4))

Output:

1
4

Insert while preserving order:

from bisect import insort

values = [2, 4, 7, 9]

insort(values, 5)

print(values)

Output:

[2, 4, 5, 7, 9]

Important detail:

Finding the insertion position is:

O(log n)

But inserting into the middle of a Python list requires shifting elements:

O(n)

So insort is still:

O(n)

overall.

Binary search finds the parking spot quickly.

The entire row of cars still needs to move.

---

📉 Binary Search on Descending Data

Binary search also works on descending data, but comparisons must be reversed.

def binary_search_descending(values, target):
    left = 0
    right = len(values) - 1

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

        if values[middle] == target:
            return middle

        if target > values[middle]:
            right = middle - 1
        else:
            left = middle + 1

    return -1

For:

values = [100, 80, 60, 40, 20]

The ordering is still consistent.

Binary search does not require ascending order specifically.

It requires predictable order.

---

🔄 Search in a Rotated Sorted Array

A rotated sorted array may look like:

values = [40, 50, 60, 70, 10, 20, 30]

It was originally:

10, 20, 30, 40, 50, 60, 70

and then rotated.

We can still search in O(log n) by identifying which half is sorted.

def search_rotated(values, target):
    left = 0
    right = len(values) - 1

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

        if values[middle] == target:
            return middle

        if values[left] <= values[middle]:
            if values[left] <= target < values[middle]:
                right = middle - 1
            else:
                left = middle + 1
        else:
            if values[middle] < target <= values[right]:
                left = middle + 1
            else:
                right = middle - 1

    return -1

This is a classic interview problem.

Binary search looks at the array and says:

“Fine. You rotated the data. I will still find the sorted half.”

---

⛰️ Find a Peak Element

A peak is an element greater than its neighbours.

Example:

values = [1, 3, 7, 12, 9, 4, 2]

12 is a peak.

def find_peak(values):
    left = 0
    right = len(values) - 1

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

        if values[middle] < values[middle + 1]:
            left = middle + 1
        else:
            right = middle

    return left

Time:

O(log n)

This works because the local slope tells us which direction contains a peak.

If the sequence is rising, move right.

If it is falling, keep the current point or move left.

---

🧮 Binary Search on the Answer

This is the most powerful version of binary search.

Sometimes we are not searching inside a list.

We are searching for the smallest or largest value that satisfies a condition.

The pattern looks like:

def binary_search_answer(low, high, is_valid):
    answer = None

    while low <= high:
        middle = low + (high - low) // 2

        if is_valid(middle):
            answer = middle
            high = middle - 1
        else:
            low = middle + 1

    return answer

This finds the smallest valid answer.

To find the largest valid answer, reverse the boundary update.

---

✅ The Monotonic Condition

Binary search on the answer works only when validity changes in one direction.

Example:

Candidate:  1  2  3  4  5  6  7
Valid?:     N  N  N  Y  Y  Y  Y

There is a clear boundary.

Binary search finds the first Y.

Another form:

Candidate:  1  2  3  4  5  6  7
Valid?:     Y  Y  Y  Y  N  N  N

Binary search can find the last Y.

If validity behaves like:

Y N Y N Y

binary search cannot safely eliminate half the range.

That is not monotonic.

That is a mood swing.

---

🤖 AI Use Case 1: Largest Batch Size That Fits in GPU Memory

Suppose we want the largest batch size that does not cause an out-of-memory error.

Conceptually:

Batch size:  1  2  4  8  16  32  64
Fits?:       Y  Y  Y  Y   Y   N   N

A simplified search:

def largest_safe_batch_size(
    minimum,
    maximum,
    fits_in_memory
):
    answer = 0
    left = minimum
    right = maximum

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

        if fits_in_memory(middle):
            answer = middle
            left = middle + 1
        else:
            right = middle - 1

    return answer

Example mock condition:

def fits_in_memory(batch_size):
    return batch_size <= 24

Usage:

print(
    largest_safe_batch_size(
        1,
        128,
        fits_in_memory
    )
)

Output:

24

Real GPU memory can be affected by fragmentation, sequence length, model state, and caching, so production tests require careful cleanup and repeated measurements.

But the binary-search pattern remains useful.

---

🧠 AI Use Case 2: Maximum Context That Meets a Latency Target

Suppose an application must respond within 2 seconds.

Longer context generally increases processing time.

Tokens:       500  1000  2000  4000  8000
Under 2 sec?:  Y     Y     Y     N     N

Search for the largest token count that meets the latency requirement.

def largest_context_within_latency(
    minimum_tokens,
    maximum_tokens,
    meets_latency_target
):
    answer = 0
    left = minimum_tokens
    right = maximum_tokens

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

        if meets_latency_target(middle):
            answer = middle
            left = middle + 1
        else:
            right = middle - 1

    return answer

This can help tune:

• Prompt size

• Retrieved document count

• Chunk count

• Generation length

• Batch size

Again, the condition must be reasonably monotonic.

Real latency may contain noise, so use repeated measurements or a stable estimate.

---

📚 AI Use Case 3: RAG Metadata and Timestamp Search

A RAG system may store documents sorted by:

• Date

• Version

• Numeric ID

• Relevance threshold

• Document length

Suppose timestamps are sorted.

Binary search can find the first document created after a given time.

from bisect import bisect_left

timestamps = [
    1700000000,
    1700001000,
    1700002000,
    1700003000
]

query_time = 1700001500

position = bisect_left(timestamps, query_time)

print(position)

Output:

2

This is useful for range filtering before retrieval.

Important distinction:

Binary search does not directly solve nearest-neighbour search over high-dimensional embeddings.

Embedding vectors are not naturally arranged in one simple sorted order.

Vector databases use specialised indexes such as graph-based or partition-based structures.

Binary search may still be used around scalar metadata, thresholds, sorted scores, or internal boundaries.

Do not binary-search a 1,536-dimensional embedding and expect the AI gods to approve.

---

🎚️ AI Use Case 4: Finding the Smallest Confidence Threshold

Suppose a classifier produces a confidence score.

We want the smallest threshold that achieves a required precision level.

Conceptually:

Threshold:          0.10  0.20  0.30  0.40  0.50
Required precision?   N     N     Y     Y     Y

If the evaluation behaves monotonically enough, binary search can locate the first acceptable threshold.

def smallest_valid_threshold(
    minimum,
    maximum,
    is_valid,
    precision=1e-4
):
    left = minimum
    right = maximum

    while right - left > precision:
        middle = (left + right) / 2

        if is_valid(middle):
            right = middle
        else:
            left = middle

    return right

This is binary search over floating-point values.

The loop does not wait for exact equality.

Floating-point numbers are excellent at many things.

Agreeing that two calculations are exactly equal is not always one of them.

We stop when the range is sufficiently small.

---

🧪 AI Use Case 5: Choosing a Model Configuration

Suppose several model configurations are sorted by memory usage:

models = [
    ("Tiny", 2),
    ("Small", 4),
    ("Medium", 8),
    ("Large", 16),
    ("Huge", 32)
]

Your machine has 10 GB available for the model.

You want the largest configuration that fits.

def largest_model_that_fits(models, memory_limit):
    left = 0
    right = len(models) - 1
    answer = None

    while left <= right:
        middle = left + (right - left) // 2
        name, required_memory = models[middle]

        if required_memory <= memory_limit:
            answer = models[middle]
            left = middle + 1
        else:
            right = middle - 1

    return answer

Usage:

print(largest_model_that_fits(models, 10))

Output:

('Medium', 8)

This simplified example can represent choices sorted by:

• Memory requirement

• Parameter count

• Latency

• Cost

• Context window

• Throughput requirement

The real configuration may involve multiple dimensions.

Binary search works when the decision can be reduced to one ordered, monotonic dimension.

---

🪜 AI Use Case 6: Finding the Minimum Number of Workers

Suppose an inference queue must be processed within a target time.

As the number of workers increases, completion time generally decreases.

Workers:          1   2   3   4   5   6
Meets deadline?:  N   N   N   Y   Y   Y

Find the minimum valid number:

def minimum_workers(
    minimum,
    maximum,
    meets_deadline
):
    answer = None
    left = minimum
    right = maximum

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

        if meets_deadline(middle):
            answer = middle
            right = middle - 1
        else:
            left = middle + 1

    return answer

This pattern can help with:

• Inference replicas

• Data-processing workers

• Parallel embedding jobs

• Queue consumers

• Shards

• Provisioned throughput

Real systems include noisy performance and warm-up behaviour, so benchmark carefully.

An algorithm can help choose the candidates.

It cannot convince a cold container to become warm through positive thinking.

---

📈 AI Use Case 7: Searching Sorted Evaluation Results

Suppose model evaluation scores are sorted:

scores = [0.51, 0.62, 0.69, 0.74, 0.81, 0.88]

Find the first model meeting a required score:

from bisect import bisect_left

required_score = 0.75

position = bisect_left(scores, required_score)

if position < len(scores):
    print(scores[position])
else:
    print("No model meets the requirement")

Output:

0.81

This may be useful when searching candidates ordered by a scalar metric.

However, model selection is rarely based on one number alone.

Accuracy, latency, memory, fairness, reliability, and cost may all matter.

Binary search can locate a boundary.

It cannot decide your product strategy.

---

🔑 Searching Objects with a Key

The data does not need to be plain integers.

Suppose records are sorted by token_count.

documents = [
    {"name": "Doc A", "token_count": 120},
    {"name": "Doc B", "token_count": 350},
    {"name": "Doc C", "token_count": 700},
    {"name": "Doc D", "token_count": 1100}
]

Search for an exact token count:

def binary_search_by_key(
    items,
    target,
    key
):
    left = 0
    right = len(items) - 1

    while left <= right:
        middle = left + (right - left) // 2
        middle_value = key(items[middle])

        if middle_value == target:
            return middle

        if middle_value < target:
            left = middle + 1
        else:
            right = middle - 1

    return -1

Usage:

position = binary_search_by_key(
    documents,
    700,
    key=lambda document: document["token_count"]
)

print(documents[position])

Output:

{'name': 'Doc C', 'token_count': 700}

The records must already be sorted using the same key.

Sorting by name and searching by token_count is a disagreement between departments.

Binary search will not mediate.

---

🧠 A Reusable Lower-Bound Function with a Key

def lower_bound_by_key(
    items,
    target,
    key
):
    left = 0
    right = len(items)

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

        if key(items[middle]) < target:
            left = middle + 1
        else:
            right = middle

    return left

Example:

position = lower_bound_by_key(
    documents,
    500,
    key=lambda document: document["token_count"]
)

print(position)
print(documents[position])

Output:

2
{'name': 'Doc C', 'token_count': 700}

It finds the first document whose token count is at least 500.

---

🔢 Integer Square Root Using Binary Search

Find the largest integer whose square is no greater than number.

def integer_square_root(number):
    if number < 0:
        raise ValueError("Number cannot be negative")

    left = 0
    right = number
    answer = 0

    while left <= right:
        middle = left + (right - left) // 2
        square = middle * middle

        if square <= number:
            answer = middle
            left = middle + 1
        else:
            right = middle - 1

    return answer

Usage:

print(integer_square_root(27))

Output:

5

Because:

5² = 25
6² = 36

This demonstrates binary search on a numeric answer space.

---

📦 Minimum Capacity Problems

A common interview pattern asks:

What is the minimum capacity required to complete work within a given number of days?

Examples include:

• Shipping packages

• Splitting workloads

• Processing token batches

• Assigning embedding jobs

• Scheduling inference requests

The answer space might be:

Low capacity ---------------------- High capacity
Impossible        Boundary         Possible

flowchart LR
    A["Too small"] --> B["Too small"]
    B --> C["First valid capacity"]
    C --> D["Valid"]
    D --> E["Valid"]

The helper checks whether a candidate capacity is sufficient.

Binary search finds the first sufficient candidate.

This is one of the most important patterns to recognise:

Search the answer, not necessarily the original array.

---

🧩 A Standard Boundary Template

Find the first value for which condition(value) is true:

def first_true(low, high, condition):
    answer = None

    while low <= high:
        middle = low + (high - low) // 2

        if condition(middle):
            answer = middle
            high = middle - 1
        else:
            low = middle + 1

    return answer

Find the last value for which the condition is true:

def last_true(low, high, condition):
    answer = None

    while low <= high:
        middle = low + (high - low) // 2

        if condition(middle):
            answer = middle
            low = middle + 1
        else:
            high = middle - 1

    return answer

Memorising templates can help.

Understanding why the boundaries move is much better.

Without understanding, binary search code becomes ceremonial chanting.

---

🧱 Choosing Inclusive or Half-Open Boundaries

There are two popular styles.

Inclusive range

[left, right]

Both endpoints are candidates.

Typical loop:

while left <= right:

Updates often use:

right = middle - 1
left = middle + 1

Half-open range

[left, right)

left is included.

right is excluded.

Typical loop:

while left < right:

Updates may use:

right = middle
left = middle + 1

Both styles are valid.

Problems begin when code starts with one style and emotionally transitions into the other halfway through.

Choose one invariant and preserve it.

---

🧾 What Is an Invariant?

An invariant is a statement that remains true during every iteration.

For exact binary search using inclusive bounds:

If the target exists, it remains somewhere between left and right.

When we discard a half, we must be certain that half cannot contain the target.

Thinking in invariants prevents random pointer movement.

Without an invariant, developers often change +1 to -1 until the tests become quiet.

That is not debugging.

That is negotiating with the algorithm.

---

🚨 Common Binary Search Mistakes

1. Searching Unsorted Data

values = [8, 2, 19, 4]

Binary search cannot make reliable decisions.

2. Using the Wrong Loop Condition

Confusing:

left <= right

with:

left < right

without adjusting the boundary model.

3. Not Moving Past the Middle

Wrong:

left = middle

in an inclusive search may cause an infinite loop.

Often the correct update is:

left = middle + 1

4. Discarding the Target

Wrong boundary updates may skip a valid candidate.

5. Returning Immediately When Finding Duplicates

For first or last occurrence, save the answer and keep searching.

6. Forgetting Empty Input

values = []

The implementation should safely return “not found.”

7. Assuming Every Condition Is Monotonic

Binary search cannot search arbitrary true/false patterns.

8. Using Exact Equality for Floating-Point Search

Stop using a tolerance:

while right - left > precision:

9. Ignoring the Cost of Sorting

Binary search is fast after sorting.

Sorting is not free.

10. Using It Directly for High-Dimensional Embeddings

Vector similarity search requires specialised indexing.

A sorted scalar list and an embedding space are not the same thing.

---

🧪 Testing Binary Search Properly

Test more than one happy path.

def test_binary_search():
    values = [2, 5, 8, 12, 19, 31]

    assert binary_search(values, 2) == 0
    assert binary_search(values, 31) == 5
    assert binary_search(values, 12) == 3
    assert binary_search(values, 99) == -1
    assert binary_search([], 10) == -1
    assert binary_search([7], 7) == 0
    assert binary_search([7], 8) == -1

For duplicates:

def test_boundaries():
    values = [2, 4, 4, 4, 9]

    assert find_first(values, 4) == 1
    assert find_last(values, 4) == 3
    assert count_occurrences(values, 4) == 3
    assert count_occurrences(values, 8) == 0

Important test categories:

• Empty list

• One element

• Two elements

• First element

• Last element

• Middle element

• Missing target

• Duplicate values

• All values equal

• Descending order

• Boundary answer

• No valid answer

• Every answer valid

Binary search usually works beautifully in the middle.

The boundaries are where it begins writing plot twists.

---

🌳 Binary Search vs Binary Search Tree

These names sound similar but refer to different things.

Binary search

An algorithm that searches an ordered range by repeatedly halving it.

Typical array complexity:

O(log n)

Binary search tree

A node-based data structure where:

• Smaller values usually go left

• Larger values usually go right

Search complexity depends on the tree shape.

Balanced tree:

O(log n)

Highly unbalanced tree:

O(n)

Binary search is an algorithm.

A binary search tree is a data structure.

They are related through ordering, but they are not interchangeable.

A binary search tree is not “binary search wearing branches.”

Although visually, it is not helping its case.

---

🧠 Binary Search vs Hash Table

A hash table can provide average:

O(1)

exact key lookup.

So why use binary search?

Binary search supports ordered questions such as:

• First value at least x

• Last value below x

• Values inside a range

• Closest insertion position

• Boundary of a monotonic condition

A hash table is excellent for:

“Does this exact key exist?”

Binary search is excellent for:

“Where does this value belong in the order?”

Different questions.

Different tools.

---

🗄️ Binary Search and Databases

Databases often use tree-based indexes rather than binary searching a raw file.

However, the underlying principle remains related:

Use ordering to eliminate large regions of impossible answers.

Database indexes support:

• Ordered lookups

• Range queries

• Prefix scans

• Boundary searches

In an AI application, indexed metadata can filter candidate documents before expensive embedding or model operations.

The cheapest token is often the one you never send to the model.

---

🧮 When Binary Search Is Worth Using

Use it when:

• Data is already sorted

• The same collection is searched repeatedly

• Random access is efficient

• The input is large

• You need lower or upper bounds

• The condition is monotonic

• You need a first-valid or last-valid answer

• A feasibility test is cheaper than checking every candidate

Do not force it when:

• Data is unsorted and searched once

• The input is tiny

• The structure has slow middle access

• The condition is not monotonic

• A dictionary provides simpler exact lookup

• A specialised vector index is required

• The measurement is too noisy to form a stable boundary

Binary search is powerful.

But not every problem becomes smarter after adding middle.

---

🎤 Common Interview Questions

Why is binary search O(log n)?

Because each comparison removes approximately half the remaining search space.

Why must the data be sorted?

The comparison with the middle value must tell us which half cannot contain the target.

Why is binary search usually better on arrays than linked lists?

Arrays offer constant-time middle access. Linked lists require traversal.

What is the difference between lower and upper bound?

Lower bound finds the first value greater than or equal to the target.

Upper bound finds the first value strictly greater than the target.

How do you find the first occurrence of a duplicate?

Save the matching index and continue searching left.

How do you find the last occurrence?

Save the match and continue searching right.

What is binary search on the answer?

Search a numeric or ordered candidate space for the first or last value satisfying a monotonic condition.

Can binary search work on floating-point values?

Yes. Stop when the interval is smaller than a chosen tolerance.

Why can left = middle cause an infinite loop?

When only two candidates remain, middle may equal left, so the range does not shrink.

What is the biggest practical source of bugs?

Mixing boundary conventions and mishandling equality.

Is binary search always faster than linear search?

No. Sorting cost, tiny inputs, memory access, and one-time searches can make linear search more practical.

Can binary search directly search embeddings?

Not generally. High-dimensional nearest-neighbour search requires specialised indexes.

---

📌 Binary Search Quick Cheat Sheet

Exact search

left = 0
right = len(values) - 1

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

    if values[middle] == target:
        return middle

    if values[middle] < target:
        left = middle + 1
    else:
        right = middle - 1

Time:

O(log n)

Extra space:

O(1)

First occurrence

When found:

answer = middle
right = middle - 1

Last occurrence

When found:

answer = middle
left = middle + 1

Lower bound

Find first position where:

value >= target

Upper bound

Find first position where:

value > target

First valid answer

if condition(middle):
    answer = middle
    right = middle - 1
else:
    left = middle + 1

Last valid answer

if condition(middle):
    answer = middle
    left = middle + 1
else:
    right = middle - 1

Golden rule

Binary search works when one comparison can safely eliminate half of the remaining possibilities.

---

🛠️ Complete Reusable Python Utilities

from collections.abc import Callable, Sequence
from typing import TypeVar

T = TypeVar("T")


def binary_search(
    values: Sequence[T],
    target: T
) -> int:
    left = 0
    right = len(values) - 1

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

        if values[middle] == target:
            return middle

        if values[middle] < target:
            left = middle + 1
        else:
            right = middle - 1

    return -1


def lower_bound(
    values: Sequence[T],
    target: T
) -> int:
    left = 0
    right = len(values)

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

        if values[middle] < target:
            left = middle + 1
        else:
            right = middle

    return left


def upper_bound(
    values: Sequence[T],
    target: T
) -> int:
    left = 0
    right = len(values)

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

        if values[middle] <= target:
            left = middle + 1
        else:
            right = middle

    return left


def first_true(
    low: int,
    high: int,
    condition: Callable[[int], bool]
) -> int | None:
    answer = None

    while low <= high:
        middle = low + (high - low) // 2

        if condition(middle):
            answer = middle
            high = middle - 1
        else:
            low = middle + 1

    return answer


def last_true(
    low: int,
    high: int,
    condition: Callable[[int], bool]
) -> int | None:
    answer = None

    while low <= high:
        middle = low + (high - low) // 2

        if condition(middle):
            answer = middle
            low = middle + 1
        else:
            high = middle - 1

    return answer

Example:

values = [2, 4, 4, 4, 7, 11]

print(binary_search(values, 7))
print(lower_bound(values, 4))
print(upper_bound(values, 4))

largest_safe = last_true(
    1,
    128,
    condition=lambda batch: batch <= 24
)

print(largest_safe)

Output:

4
1
4
24

---

✅ A Mental Checklist Before Writing Binary Search

Ask:

• Is the data sorted?

• If not, is sorting worthwhile?

• What exactly am I searching for?

• Exact match, first match, last match, or insertion point?

• Is the range inclusive or half-open?

• What does left represent?

• What does right represent?

• Does every update shrink the range?

• Can the target be at the first or last position?

• Are duplicates possible?

• Is the condition monotonic?

• What happens when no answer exists?

• Am I using integer or floating-point search?

• Is middle access efficient?

• Is a built-in function such as bisect more appropriate?

• Am I solving a scalar ordered problem or mistakenly treating an embedding space as one?

If these questions have clear answers, the code usually becomes much easier.

---

🎯 Final Thoughts

Binary search begins with a surprisingly simple idea:

Check the middle and remove the impossible half.

But that idea expands far beyond finding one number in a sorted array.

It helps us solve:

• Exact searches

• Duplicate boundaries

• Insertion positions

• Rotated arrays

• Peak finding

• Threshold selection

• Capacity planning

• Batch-size tuning

• Context-length tuning

• Resource allocation

• First-valid and last-valid problems

In the age of AI, binary search remains valuable because AI engineering is full of boundaries:

• How much context can we process?

• What batch size fits?

• Which model meets the requirement?

• What threshold produces acceptable quality?

• How many workers meet the deadline?

• Where does this timestamp belong?

• What is the smallest configuration that works?

Binary search does not understand language.

It does not generate images.

It cannot explain why the model hallucinated.

But it can reduce one billion possible answers to about thirty decisions.

That is a useful colleague.

So the next time your code searches every option one by one, ask:

“Is this problem ordered—and can I confidently throw away half?”

If the answer is yes, binary search may save time, compute, memory, cloud cost, and perhaps the remaining patience of your engineering team.

Because intelligent systems are not built only with intelligent models.

They are also built with algorithms intelligent enough to stop looking where the answer cannot be. 🤖🔍🚀

---

🌐 Let’s Connect

Whether you are learning algorithms, preparing for interviews, tuning an AI workload, or changing left = middle + 1 for the seventh time while hoping the tests finally pass, I am always happy to connect.

Let us continue building AI systems that are not only intelligent, but also efficient, understandable, and supported by strong computer-science foundations.

LinkedIn: Connect with me for AI, AWS, cloud engineering, Python, and software-development content.
hardeepjethwani@LinkedIn

TopMate: Looking for guidance, brainstorming, or a technical discussion over a virtual coffee?
hardeepjethwani@TopMate

Instagram: Follow my learning journey, technology experiments, and behind-the-scenes builder content.
hardeepjethwani@Instagram

X: Join the conversation around AI, cloud, Python, algorithms, and developer humour.
hardeepjethwani@X

Want to support my AI, cloud, and educational adventures? Feel free to buy me a virtual coffee.

Binary search can locate the correct coffee size in O(log n).

Unfortunately, drinking it still takes O(n). ☕😂

---

#BinarySearch #Algorithms #DataStructures #DSA #Python #ArtificialIntelligence #AIEngineering #TimeComplexity #SpaceComplexity #MachineLearning #GenerativeAI #PythonProgramming #SoftwareEngineering #ComputerScience #Coding #Programming #TechEducation #DeveloperCommunity #BeginnerFriendly #InterviewPreparation