How many comparisons does binary search need?

The count grows on the order of log base 2 of the number of candidates, with exact bounds depending on the variant.

Can it search text labels?

Yes, if labels are sorted and compared using a consistent ordering.

Does it need a neural network?

No. It is a classical algorithm based on ordered comparisons.

AI Glossary / Graphs and symbolic AI / Beginner

Binary search

Definition

Binary search finds a target or a boundary in an ordered search space by repeatedly examining a middle position and discarding the half that cannot contain the answer. For a sorted array with efficient indexed access, it needs logarithmically many comparisons.

What it means

The method works because ordering makes a comparison informative about many other positions. If the middle value is smaller than the target in an ascending sequence, every earlier value is also too small. The search can eliminate that entire portion without examining each item.

Binary search does not sort the data. Its correctness depends on the relevant ordering already holding and on comparisons using that same ordering. Searching a list sorted by product name using product price breaks the central assumption.

The target may be an exact value, the first value at least as large as a threshold, or the position where a new value should be inserted. These are related but different questions. In particular, an insertion position is not proof that an equal value already exists.

The broader idea also works for a monotone predicate: a sequence of false results followed by true results, with one boundary to locate. It cannot generally find a boundary reliably when outcomes switch back and forth.

How it works

Maintain lower and upper bounds for the candidate interval. Inspect its midpoint and compare the middle value with the target. Depending on the comparison and the exact search variant, move one boundary past the midpoint or retain the midpoint as a possible boundary. Stop when the interval is empty or the requested answer is established.

Implementations must use one consistent convention for inclusive and exclusive endpoints. Each iteration should reduce the candidate interval; otherwise a two-element interval can cause an infinite loop. Empty arrays and answers beyond the final element also need defined results.

Duplicates require a choice. An exact-match search may return any matching position, whereas lower-bound and upper-bound searches identify the edges of an equal-value range. Python's bisect_left and bisect_right locate these insertion boundaries rather than performing an equality test.

Logarithmic comparisons do not guarantee logarithmic cost for every operation. Accessing a midpoint in a linked structure can be expensive, and inserting into a contiguous list may require moving many elements.

Three practical examples

A catalog service locates an identifier in a sorted array of identifiers, then checks whether the returned candidate actually matches.
A reporting tool finds the first timestamp at or after a selected date in chronologically ordered records.
A configuration tool locates the smallest setting that passes a test when increasing the setting is known to preserve success.

Think of it this way

Think of finding a page in a numbered book by opening near the middle and choosing the earlier or later portion. Page order lets one comparison eliminate many possibilities.

The analogy fails if pages are shuffled or the requested label is unrelated to page numbering. It also hides physical access costs: a computer array can jump directly to a position, while some storage arrangements cannot.

Worked example

Finding an insertion boundary

Take the sorted values [4, 9, 15, 22, 31, 45, 58], indexed from 0 to 6. Find the first position whose value is at least 30. Use a half-open interval [lo, hi), initially [0, 7).

The midpoint is 3, with value 22. Since 22 is below 30, move lo to 4. The remaining interval is [4, 7). Its midpoint is 5, with value 45, so move hi to 5. The interval becomes [4, 5). Its midpoint is 4, with value 31, so move hi to 4.

Now lo equals hi at 4. This is the insertion position for 30, before 31. Since the value at position 4 is not 30, an exact-match query should report that 30 is absent.

For target 31, the same boundary is 4 but the equality check succeeds. For a target larger than 58, the insertion position is 7, beyond the final element; attempting to read that position without a bounds check would be an error.

Illustrative case study

Fictional case: Rowan Records replaces repeated scans with a boundary search over timestamped records. The first implementation sometimes selects the wrong day because a later import appends older records without restoring chronological order.

The team makes the ordering requirement explicit, checks imports and defines how equal timestamps are handled. It also distinguishes locating the first record on a date from proving that any record exists for that date.

The lesson is that a faster search method relies on maintained data properties. A correct search routine can still return misleading results when its input contract has been broken.

Common misconceptions and mistakes

Binary search works on any list. The required ordering or monotonicity must hold.
A returned insertion index means the item was found. Equality and bounds must be checked for exact lookup.
Logarithmic search means logarithmic insertion. Shifting array elements can still take linear time.
Duplicate values have one obvious answer. The desired first, last or arbitrary match must be specified.
Binary search and a binary search tree are identical. One is a search procedure; the other is a data structure with its own shape and maintenance rules.

Business use

Binary search is useful for repeated lookups and threshold queries over stable ordered data.

Evaluate the complete workload: sorting, updates, key extraction and search all contribute to cost. If records change while a search is running, use an appropriate consistency mechanism so the ordering does not shift underneath it. For monotone-test applications, validate monotonicity rather than assuming that a larger parameter always improves the result.

Check your understanding

A lower-bound search for 12 returns position 2 in [3, 8, 14, 20]. Is 12 present?

Answer: No. Position 2 identifies where 12 could be inserted before 14. An equality check distinguishes an insertion boundary from a matching value.

Related terms

Linear search
Indexing
Sorted array
logarithmic complexity
lower bound
upper bound
monotone predicate
binary search tree

Learn next

Trace the worked array for targets smaller than 4, equal to 22 and larger than 58. Write down the interval after every step. Then add repeated values and compare the first permitted insertion position with the last permitted insertion position.

Sources

Python documentation, bisect boundary semantics, duplicate handling and insertion-cost distinction: https://docs.python.org/3/library/bisect.html

NIST Dictionary of Algorithms and Data Structures, binary search: https://xlinux.nist.gov/dads/HTML/binarySearch.html

The array trace and fictional records example are original illustrations.

Previous: Binary resolution Next: Binary variable