Data Structures and Algorithms · Searching and sorting

Binary search

Repeatedly halving a sorted range to find a target in logarithmic time.

Also known as: binary search on sorted array, log-time search.

Start a lesson on Binary search

Learn first

• Arrays: A fixed-layout, contiguous block of memory where any index is reached in constant time.

Leads to

• Binary search trees: A binary tree kept ordered so each node's left subtree is smaller and right subtree is larger.

Related topics

• Two pointers: Walking two indices through a sequence at once to avoid a nested loop.
• Divide and conquer: Splitting a problem into independent smaller copies of itself, solving each, then combining.