FoundationSource checked

Binary Search

Finds a target or insertion point in sorted data by repeatedly halving the candidate range.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Searching
Difficulty: Beginner
Family: Divide and Conquer
Tier: Foundation
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 1
Relationships: 19
Code example: Ready
Visualization: Ready
Aliases: Half-Interval Search

Overview

Binary Search compares the target with the middle item of a sorted range. Each comparison discards the half of the range that cannot contain the answer.

Core Concepts

sorted search spacemidpoint comparisoninterval invariantmonotone predicate

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(1)

Average

O(log n)

Worst

O(log n)

Space

O(1)

When to Use

Use it when the data is sorted or the predicate is monotone.
Use it when random access is available.
Use it when O(log n) lookup is worth maintaining sorted order.

When Not to Use

Avoid it when the input cannot be kept sorted cheaply.
Avoid it on linked lists or streams without efficient random access.
Avoid it when equality or ordering is inconsistent.

What It Does

Searches sorted collections
Maintains a shrinking candidate interval

Use Cases

Finding items in sorted arrays
Finding insertion points
Searching monotone predicates

Inputs

Sorted array or list
Target value

Outputs

Index of target
Not-found result
Insertion position

Key Formulas (1)

Midpoint index

mid = low + ⌊(high − low) / 2⌋

mid = low + floor((high - low) / 2)

Chooses the middle of the active search interval while avoiding overflow in some languages.

Pseudocode

1.Set low to 0 and high to length - 1
2.While low is less than or equal to high:
3.Check the middle item
4.If the middle item matches the target, return its index
5.If the target is smaller, move high left
6.If the target is larger, move low right

Canonical Example

Input: array = [2, 5, 8, 12, 16], target = 12
Output: index = 3
Explanation: The first midpoint is 8, so the search keeps the right half and then finds 12.

Implementation Notes

Choose either inclusive bounds or half-open bounds and keep that convention throughout.
Compute the midpoint in a way that avoids overflow in fixed-width integer languages.
Decide whether not-found returns a sentinel, boolean, or insertion position.