# 🔍 Binary Search in the Age of AI

**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:

```text
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:

```text
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:

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

Incorrect:

```python
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:

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

Search for:

```python
target = 31
```

Start with three positions:

```text
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`:

```mermaid
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

```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:

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

position = binary_search(values, 31)

print(position)
```

Output:

```text
5
```

When the value does not exist:

```python
print(binary_search(values, 99))
```

Output:

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

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

You may also see:

```python
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`

```python
while left <= right:
```

When `left == right`, one candidate remains.

That final candidate still needs to be checked.

Using:

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

```text
n
n / 2
n / 4
n / 8
...
1
```

The number of halvings is approximately:

```text
log₂(n)
```

Therefore:

```text
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:

```text
left, right, middle
```

Extra space:

```text
O(1)
```

* * *

# 🔁 Recursive Binary Search

```python
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:

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

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

print(position)
```

Time:

```text
O(log n)
```

Call-stack space:

```text
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:

```text
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:

```text
O(1)
```

indexed access.

Linked lists require:

```text
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:

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

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

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

```python
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:

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

print(find_first(values, 4))
```

Output:

```text
1
```

Time:

```text
O(log n)
```

* * *

# ➡️ Find the Last Occurrence

When the target is found, continue searching right.

```python
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:

```python
print(find_last(values, 4))
```

Output:

```text
3
```

* * *

# 🔢 Count Occurrences

```python
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:

```python
print(count_occurrences(values, 4))
```

Output:

```text
3
```

Complexity:

```text
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:

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

Where should `35` be inserted to preserve sorting?

Answer:

```text
Index 3
```

```python
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:

```python
print(insertion_position(scores, 35))
```

Output:

```text
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:

```text
value >= target
```

## Upper bound

The first index where:

```text
value > target
```

```python
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:

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

For target `4`:

```text
lower bound = 1
upper bound = 4
```

The count is:

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

Output:

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

```python
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:

```text
1
4
```

Insert while preserving order:

```python
from bisect import insort

values = [2, 4, 7, 9]

insort(values, 5)

print(values)
```

Output:

```text
[2, 4, 5, 7, 9]
```

Important detail:

Finding the insertion position is:

```text
O(log n)
```

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

```text
O(n)
```

So `insort` is still:

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

```python
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:

```python
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:

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

It was originally:

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

and then rotated.

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

```python
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:

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

`12` is a peak.

```python
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:

```text
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:

```python
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:

```text
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:

```text
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:

```text
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:

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

A simplified search:

```python
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:

```python
def fits_in_memory(batch_size):
    return batch_size <= 24
```

Usage:

```python
print(
    largest_safe_batch_size(
        1,
        128,
        fits_in_memory
    )
)
```

Output:

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

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

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

```python
from bisect import bisect_left

timestamps = [
    1700000000,
    1700001000,
    1700002000,
    1700003000
]

query_time = 1700001500

position = bisect_left(timestamps, query_time)

print(position)
```

Output:

```text
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:

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

```python
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:

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

```python
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:

```python
print(largest_model_that_fits(models, 10))
```

Output:

```text
('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.

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

Find the minimum valid number:

```python
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:

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

Find the first model meeting a required score:

```python
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:

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

```python
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:

```python
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:

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

print(documents[position])
```

Output:

```text
{'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

```python
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:

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

print(position)
print(documents[position])
```

Output:

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

```python
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:

```python
print(integer_square_root(27))
```

Output:

```text
5
```

Because:

```text
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:

```text
Low capacity ---------------------- High capacity
Impossible        Boundary         Possible
```

```mermaid
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:

```python
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:

```python
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

```text
[left, right]
```

Both endpoints are candidates.

Typical loop:

```python
while left <= right:
```

Updates often use:

```python
right = middle - 1
left = middle + 1
```

## Half-open range

```text
[left, right)
```

`left` is included.

`right` is excluded.

Typical loop:

```python
while left < right:
```

Updates may use:

```python
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

```python
values = [8, 2, 19, 4]
```

Binary search cannot make reliable decisions.

## 2\. Using the Wrong Loop Condition

Confusing:

```python
left <= right
```

with:

```python
left < right
```

without adjusting the boundary model.

## 3\. Not Moving Past the Middle

Wrong:

```python
left = middle
```

in an inclusive search may cause an infinite loop.

Often the correct update is:

```python
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

```python
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:

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

```python
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:

```python
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:

```text
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:

```text
O(log n)
```

Highly unbalanced tree:

```text
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:

```text
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

```python
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:

```text
O(log n)
```

Extra space:

```text
O(1)
```

## First occurrence

When found:

```python
answer = middle
right = middle - 1
```

## Last occurrence

When found:

```python
answer = middle
left = middle + 1
```

## Lower bound

Find first position where:

```text
value >= target
```

## Upper bound

Find first position where:

```text
value > target
```

## First valid answer

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

## Last valid answer

```python
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

```python
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:

```python
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:

```text
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