# Binary Search

Locating an element in a sorted sequence by repeatedly halving the search interval, achieving logarithmic time.

**Leads to:** Balanced Trees and B-Trees

**Rests on nothing.** A place to start.

*Machine Learning · Algorithms and Complexity*


## Why learn this

Binary search is the method used whenever you need to find one item in a massive list that has already been sorted, and you want the answer immediately. It is the engine behind how your phone finds a contact name in an instant, how a navigation app calculates the route from millions of roads, and how databases retrieve records without scanning every single file on the disk. Without this method, searching large datasets would require looking at almost every item one by one, which takes too long for any practical use. Mastering it gives you the ability to turn a task that feels like digging through a haystack into one that feels like opening a book to the right page.


## The intuition

Suppose you have a phone book with 1,000 pages, and you need to find the name 'Raman'. You could start on page 1 and flip forward one page at a time, checking every name. If you were unlucky, that would take 1,000 flips. But nobody actually does that. You open the book roughly in the middle, see that 'M' is there, and you know immediately that 'Raman' (which starts with 'R') cannot be anywhere in the first half — 'R' comes after 'M' alphabetically, so the first half of the book is entirely 'A'-to-'M' names. You throw away that half without looking at a single page of it. Now your book is half the size. You open the middle of the remaining half, see 'S', and know that 'Raman' must be before 'S', so the second half of what remains is useless. Half again. Each time you look at exactly one page, and you eliminate half of every page you did not look at. After a handful of checks, you are down to one page, and there is the name. That is binary search: you are not searching faster — you are searching *less* by eliminating half the remaining search space with every single comparison. The word 'binary' just means 'two choices' — each step asks: is what I want in the left half or the right half? And then you move to that half and ask again. The key trick works only because the data has an order: alphabetical order in the phone book, or numeric order in a sorted list of numbers. If the pages were in random order, opening to the middle would tell you nothing about where 'Raman' is — you could not eliminate anything. Order is what makes halving possible. That is why binary search requires sorted input: the order is what tells you which half to discard. With a million entries, the difference is stark. Checking one by one could take a million steps. Binary search needs at most about twenty comparisons — because 2 raised to the 20th power is already over a million, so twenty halvings reduce any search space of that size to a single item. Twenty checks versus a million. That is the whole point of the algorithm.


## An analogy

Think of finding a word in a dictionary. You do not start at 'A' and read every entry. You open roughly halfway, see the word 'M'. Your word begins with 'P', so you know the first half of the dictionary — everything from 'A' through 'M' — is useless. You do not glance at it again. You now have a dictionary that is half the size. Open that in the middle, see 'R'. Your 'P' is before 'R', so the entire back half of what remains is thrown away. Now you are holding a dictionary a quarter of the original size. Open the middle again, see 'O'. 'P' is after 'O', so the front half of this quarter goes. Each glance at one page eliminates half of the remaining book. After a handful of glances, the book is reduced to a single page carrying your word. This analogy works beautifully because the mechanism is identical: each comparison halves the search space, and the order of the entries is what makes the halving valid. The analogy stops working in one particular way: the dictionary looks up words, which have a natural order (alphabetical), but binary search works on anything with a comparable order — numbers, timestamps, or even a list of names sorted by last name.


## Definition

Binary search is a method for finding a specific item in a sorted list by repeatedly checking the middle item and discarding the half of the list that cannot contain the target, until only the target remains.


## How it connects

This concept sits directly beside Linear Search, which is the naive approach of checking items one by one from start to finish, and Binary Trees, which are a data structure designed to keep items sorted so you can jump between them like pages in a book. While Linear Search tells you how slow it is to do nothing but look at every option, Binary Trees show you how to organize your data physically or digitally so that the halving strategy works efficiently without jumping back and forth across a flat list.


## The mathematics

The mathematics that binary search rests on is simple arithmetic: addition, subtraction, division, and rounding down to the nearest whole number. There is no algebra, no calculus, and no geometry. The only new idea you need is a concept called *logarithms*. 

A logarithm answers one specific question: 'How many times must I cut this number in half before it becomes 1 or less?' We use base-2 because 'cutting in half' is the operation we are counting.

Let us look at the number 32. 
First halving: 32 divided by 2 is 16.
Second halving: 16 divided by 2 is 8.
Third halving: 8 divided by 2 is 4.
Fourth halving: 4 divided by 2 is 2.
Fifth halving: 2 divided by 2 is 1.
We performed five halvings. Therefore, the base-2 logarithm of 32 is 5. We write this as log₂(32) = 5.

Let us look at a larger number, 1000. 
Halving 1000 repeatedly:
1000 / 2 = 500
500 / 2 = 250
250 / 2 = 125
125 / 2 = 62.5
62.5 / 2 = 31.25
31.25 / 2 = 15.625
15.625 / 2 = 7.8125
7.8125 / 2 = 3.90625
3.90625 / 2 = 1.953125
1.953125 / 2 = 0.9765625
After ten halvings, the number is less than 1. So log₂(1000) is approximately 10.

This logarithm tells us exactly how many steps binary search takes. At each step, the algorithm cuts the remaining list of candidates in half. The number of steps required to reduce a list of size n to a single item is the number of times you can halve n. This is log₂(n).

The other arithmetic tool is finding the *middle* of a range. If you have a lower bound L and an upper bound H, the middle M is found by adding them together and dividing by 2. 
M = (L + H) divided by 2.

Because list positions are whole numbers, we cannot always land exactly on the middle if the sum is odd. In that case, we round down to the nearest whole number. This is called 'floor'. For example, if L + H equals 7, then 7 divided by 2 is 3.5. Rounding down gives us 3.

The algorithm proceeds as follows:

1. Start with two markers: low (the position of the first element in the current search range) and high (the position of the last element). Initially, low is 0 and high is n minus 1, where n is the total number of items in the list.
2. Repeat the following steps as long as low is less than or equal to high:
   a. Calculate the middle position: add low and high together, divide by 2, and round down. Let us call this mid.
   b. Look at the item at position mid in the list.
   c. If that item is exactly the target you are looking for, stop. You have found it.
   d. If that item is smaller than the target, the target must be in the upper half of the current range. Discard the lower half by setting low to mid plus 1.
   e. If that item is larger than the target, the target must be in the lower half. Discard the upper half by setting high to mid minus 1.
3. If the loop ends because low is greater than high, the target is not in the list.

The maximum number of comparisons needed in the worst case is log₂(n). For a list of size n, you halve the search space at each step until only one item remains.


## A worked example

We have a sorted list of numbers: [2, 5, 7, 10, 14, 19, 23, 31]. We want to find the number 14. The list has 8 items. We will use two markers: low (the position of the first element of the current search interval) and high (the position of the last element). Positions start at 0, so the initial range is from position 0 to position 7.

Step 1: Calculate the middle position.
Add low and high: 0 + 7 = 7.
Divide by 2: 7 divided by 2 is 3.5.
Round down (floor): 3.
So, mid = 3.
We look at the item at position 3 in the list. The items are indexed 0, 1, 2, 3... so position 3 is the fourth item: 10.

Step 2: Compare the item at mid with the target.
The item is 10. The target is 14.
Is 10 equal to 14? No.
Is 10 less than 14? Yes.
Because 10 is smaller than the target, the target must be in the upper half of the current range (positions greater than 3). We discard positions 0 through 3.
Update low: set low to mid + 1. So low becomes 3 + 1 = 4.
High remains 7.
The new search interval is positions 4 through 7.

Step 3: Calculate the new middle position.
Add low and high: 4 + 7 = 11.
Divide by 2: 11 divided by 2 is 5.5.
Round down (floor): 5.
So, mid = 5.
We look at the item at position 5 in the list. The items are indexed 0, 1, 2, 3, 4, 5... so position 5 is the sixth item: 19.

Step 4: Compare the item at mid with the target.
The item is 19. The target is 14.
Is 19 equal to 14? No.
Is 19 less than 14? No.
Is 19 greater than 14? Yes.
Because 19 is larger than the target, the target must be in the lower half of the current range (positions less than 5). We discard positions 5 through 7.
Update high: set high to mid - 1. So high becomes 5 - 1 = 4.
Low remains 4.
The new search interval is positions 4 through 4. This is a single position.

Step 5: Calculate the new middle position.
Add low and high: 4 + 4 = 8.
Divide by 2: 8 divided by 2 is 4.
Round down (floor): 4.
So, mid = 4.
We look at the item at position 4 in the list. The items are indexed 0, 1, 2, 3, 4... so position 4 is the fifth item: 14.

Step 6: Compare the item at mid with the target.
The item is 14. The target is 14.
Is 14 equal to 14? Yes.
We have found the target.

Result: The number 14 is found at position 4 in the list. We made 3 comparisons (at positions 3, 5, and 4). For a list of 8 elements, the maximum number of comparisons is log₂(8) = 3. We used exactly the maximum possible steps because we did not find it on the first guess.


## From scratch, in Python

```python
def binary_search(sorted_list, target):
    low = 0
    high = len(sorted_list) - 1

    while low <= high:
        mid = (low + high) // 2
        if sorted_list[mid] == target:
            return mid
        elif sorted_list[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

# Example usage:
numbers = [2, 5, 7, 10, 14, 19, 23, 31]
print(binary_search(numbers, 14))  # outputs 4
print(binary_search(numbers, 3))   # outputs -1
```


## What the code does

Let us break this down line by line. First, `def binary_search(sorted_list, target):` — here `sorted_list` and `target` are the inputs. `def` tells Python we are defining a function, which is a reusable block of code. Inside, we set `low = 0` and `high = len(sorted_list) - 1`. `len(sorted_list)` gives the number of items in the list, and we subtract 1 because positions start at 0. So for a list of 8 items, `high` is 7. This defines our search interval: from index 0 to index 7.

The `while` loop repeats the indented block as long as the condition `low <= high` is true. As soon as `low` becomes greater than `high`, there is nothing left to search and the loop ends. This is the heartbeat of binary search.

Inside the loop, `mid = (low + high) // 2` computes the middle index. The `//` is integer division — it drops the fractional part, so (0 + 7) // 2 is 3, not 3.5.

Then we compare the middle element with the target. `if sorted_list[mid] == target:` — if they match, we have found it, and we `return mid`, which gives the position back to whoever called the function. The function ends immediately at that moment.

If they do not match, `elif sorted_list[mid] < target:` — if the middle element is smaller than what we seek, the target must be to the right, so we set `low = mid + 1`. This discards the left half including the middle element, because we already know it is not the target.

The `else` covers the remaining case: the middle element is larger than the target, so the answer must be to the left. We set `high = mid - 1`.

After the `while` loop ends (because low > high), we have searched every relevant interval and found nothing, so we `return -1`. The value -1 is a convention meaning 'not found' — it is never a valid position.

The example at the bottom defines a list with 8 numbers, then calls the function twice. The first call finds 14 at position 4 and prints 4. The second looks for 3, which is not in the list, and prints -1. Try changing the numbers or the target to see the algorithm in action.


## Common misconceptions

**Binary search only works on numbers** — Binary search is for numbers. My list of names won't work.

Binary search only requires that the elements have a total order — any two elements can be compared, and the order is transitive. Names are ordered alphabetically, timestamps chronologically, and even custom objects can be made comparable. In fact: Binary search works on any sorted collection where you can ask 'is element A less than, equal to, or greater than element B?' That includes strings, dates, and any custom class with a comparison method.

**Binary search is the same as linear search but faster** — Binary search is just a faster way to look through a list one by one.

Linear search examines each element in turn, never skipping any. Binary search jumps around, using the sorted order to discard entire halves without ever looking at them. The step counts scale completely differently. In fact: Binary search does not scan; it eliminates. In a list of size n, linear search may need up to n comparisons, while binary search needs at most log₂(n). That difference is enormous — a million elements takes up to a million steps for linear, but only about 20 for binary.

**The list must be perfectly balanced or the algorithm fails** — If the list length is not a power of two, binary search will break.

The middle index is computed with integer division, which naturally handles odd and even lengths. The algorithm works for any positive size, including 1. In fact: Binary search works for any list length. The middle index might not be exactly in the centre, but it does not have to be — any consistent way of picking a split works, as long as the halves are disjoint and cover the whole range.

**Binary search requires the target to be present** — If the number is not in the list, binary search will get stuck forever.

The loop condition `low <= high` ensures termination. When low > high, the interval is empty, and the function returns 'not found'. It cannot loop forever because each iteration either returns or reduces the interval size. In fact: Binary search detects absence cleanly. If the interval ever becomes empty (low > high), the target is not in the list, and the algorithm returns a 'not found' indicator.

**Binary search is a sorting algorithm** — Binary search sorts my data for me, right?

Binary search assumes the data is already sorted. It does not sort. Sorting is a separate, more expensive operation (usually O(n log n)). In fact: Binary search finds a value in an already-sorted list. Sorting the list first is a separate step — you must either have sorted data already or pay the sorting cost before searching.

**The middle calculation is (low + high) / 2** — I just compute (low + high) / 2 and use the result as an index.

In many languages (including Python with `/`), division returns a float, and using a float as a list index raises an error. Also, in C-like languages, `low + high` can overflow if both are large. The correct way is integer arithmetic. In fact: Use integer division, `(low + high) // 2`, which truncates the remainder and stays within integer bounds. In languages with fixed-size integers, prefer `low + (high - low) // 2` to avoid overflow.


## In short

Binary search locates a target in a sorted list by repeatedly checking the middle element and discarding the half that cannot contain the target. Each comparison roughly halves the search space, so the number of steps grows like the logarithm of the list size — about 20 steps for a million elements. The algorithm hinges on maintaining a correct search interval (low to high) and updating it with low = mid + 1 or high = mid - 1 to avoid off-by-one bugs. It works on any ordered data, not just numbers. Its real-world use spans database indexing, token sampling in LLMs, retrieval systems, and hyperparameter tuning. The Python `bisect` module provides a ready-made implementation.


## Where this is used

Binary search is not just a classroom exercise; it is one of the most widely used algorithms in computing, and modern AI systems depend on it in several distinct ways.

**Large language models (LLMs) — sampling the next token.** When an LLM like GPT-4 generates text, it does not simply pick the single most probable next word every time. It builds a probability distribution over its whole vocabulary (tens of thousands of tokens) and then *samples* from that distribution. To sample, one common method is cumulative distribution inversion: you take a random number between 0 and 1, walk through the cumulative probabilities, and find the first token whose cumulative probability exceeds that number. If the probabilities were stored in a flat list, you would scan from the start every time — that is O(n) per token, and with a vocabulary of 50,000, that adds up across billions of tokens. Instead, production code keeps the cumulative probabilities in a sorted array and uses binary search to locate the threshold in O(log n) time. So every time an LLM writes a sentence, binary search is quietly running to pick each word.

**Small language models (SLMs) running on phones or laptops.** When a model is compressed to run on a device, efficiency matters even more. The token-sampling logic is the same, but the vocabulary is often trimmed to a few thousand tokens — still large enough that binary search is the natural choice. Also, small models often use integer quantisation for weights. When you quantise, you map floating-point weight values to a small set of integer levels. To decode the level back to the original value, you need to map from the integer to the nearest representable value — this mapping is often implemented as a lookup table with a sorted list of breakpoints, and binary search is used to find which interval a value falls into. So binary search appears wherever you need to convert between value spaces.

**Retrieval-Augmented Generation (RAG).** RAG systems first retrieve relevant documents from a large corpus, then hand them to an LLM to generate an answer. The retrieval step usually involves embedding each document as a vector and finding the nearest neighbours to the query embedding. A naive scan through millions of vectors is too slow. Real systems use Approximate Nearest Neighbour (ANN) indexes such as FAISS, which organise vectors into clusters or tree structures. Inside those structures, when you search, you often end up traversing a sorted list of distances or thresholds, and binary search is the standard way to find where a value falls in a sorted list. For example, FAISS's inverted file index stores lists of documents per cluster, and to find which cluster a query belongs to, a small binary search over cluster boundaries is common. So binary search is part of the machinery that lets a chatbot answer questions from a million-page knowledge base in milliseconds.

**Agentic systems that plan and call tools.** Agents use tools like web search, calculators, or code interpreters. Many of these tools expect arguments in a structured form, and the agent must decide what to pass. A classic application is determining whether a given integer parameter is within an allowed range — a binary search over the range of valid values (or over a sorted list of allowed options) tells the agent whether to ask for a different value. Also, when an agent has to read a log file or a sorted list of events to find an event at a particular timestamp, binary search is the go-to method. The agent's planning loop may also use binary search to find the smallest value that satisfies a condition — a pattern called 'binary search on the answer' — for example, finding the minimum buffer size that makes a request succeed under a latency constraint.

**Everyday applied machine learning.** Binary search appears everywhere:

*   **Hyperparameter tuning** — when you search for the best learning rate or the best number of layers, you often run a binary search on the exponent of the value (e.g., try 1e-3, then 1e-2, then 1e-4, halving the interval each time).
*   **Splitting points in decision trees** — when building a decision tree, you sort the feature values and consider each as a candidate split point. To find the optimal split that maximises information gain, you need to compare a target value against the sorted list of thresholds; binary search on the sorted thresholds lets you quickly locate the cut.
*   **Searching for the correct threshold in a classifier** — after training a classifier that outputs a confidence score, you want to pick a decision threshold such that precision or recall reaches a target. You sort the scores and binary search over them to find the threshold that gives the desired metric.
*   **Recommender systems** — when you have a list of recommended items already sorted by score, and the user asks for the top K with a minimum score, you can binary search to find the cut-off point.

**What a developer actually writes:** In Python, a developer might reach for the `bisect` module, which implements binary search on sorted lists. For instance:

```python
import bisect
position = bisect.bisect_left(sorted_list, target)
if position < len(sorted_list) and sorted_list[position] == target:
    print(f"Found at index {position}")
```

In a database system, you would see binary search in the B-tree lookup logic. In a vector database like FAISS, you would call a search method, but internally binary search runs on sorted thresholds.

**What breaks when done badly:** The classic failure is an off-by-one error — if you set `low = mid` instead of `low = mid + 1`, you can end up in an infinite loop, or you might miss the first or last element. Another failure is using binary search on an unsorted list — the results are meaningless and often wrong. A more subtle issue is using `(low + high) // 2` without considering integer overflow in languages like C or Java when `low + high` exceeds the maximum integer size — this actually happened in real systems. Finally, forgetting that the list must be sorted each time you search means you pay a sorting cost that may outweigh the search benefit; that is why the library notes say the sort cost must be amortised across searches.


---

Read this on the web: https://basavapurushottam.com/learn-ai/binary-search
