Binary Search
Last updated
Binary search finds a target value in a **sorted** array by repeatedly halving the search window. It compares the middle element with the target: a match ends the search; otherwise the half that cannot contain the target is discarded and the window shrinks to the other half. Each comparison eliminates half of the remaining elements, which is why it runs in O(log n) — searching a million sorted values takes at most about 20 comparisons.
The animation above shows the lo, mid and hi pointers and dims the eliminated half after every comparison. The one non-negotiable precondition: the array must already be sorted — on unsorted data you need linear search or a sort first (see merge sort). The same halving idea powers the binary search tree.
Time & space complexity
| Case | Complexity | Notes |
|---|---|---|
| Best case | O(1) | The middle element is the target on the first comparison. |
| Average case | O(log n) | Each comparison halves the remaining window. |
| Worst case | O(log n) | The window shrinks to a single element before matching or missing. |
| Space | O(1) | Iterative version keeps only the lo, hi and mid indices. |
Step by step
| Step | What happens |
|---|---|
| 1 | Set lo to the first index and hi to the last index of the sorted array. |
| 2 | Compute the middle index: mid = (lo + hi) // 2. |
| 3 | If a[mid] equals the target, return mid — found. |
| 4 | If a[mid] is **less** than the target, the target can only be in the right half: set lo = mid + 1. |
| 5 | If a[mid] is **greater** than the target, search the left half: set hi = mid - 1. |
| 6 | Repeat from step 2 while lo <= hi; if the window empties, the target is not in the array. |
Worked example
Searching for 5 in [1, 2, 3, 5, 7, 8, 9]:
| Pass | Window (lo..hi) | mid | a[mid] | Action |
|---|---|---|---|---|
| 1 | [1, 2, 3, 5, 7, 8, 9] (0..6) | 3 | 5 | a[3] = 5 — target found at index 3. |
A miss, step by step
Searching for 4 in the same array shows how the window empties:
| Pass | Window (lo..hi) | mid | a[mid] | Action |
|---|---|---|---|---|
| 1 | 0..6 | 3 | 5 | 5 > 4 — search the left half, hi = 2. |
| 2 | 0..2 | 1 | 2 | 2 < 4 — search the right half, lo = 2. |
| 3 | 2..2 | 2 | 3 | 3 < 4 — lo becomes 3, window empties: not found. |
When to use binary search
| Use it when | Avoid it when |
|---|---|
| The data is already sorted (or you search it many times) | The data is unsorted and searched only once — sorting first costs O(n log n) |
| The collection supports fast random access (arrays) | You only have sequential access (linked lists) |
The dataset is large — O(log n) shines at scale | The dataset is tiny — a simple scan is just as fast and simpler |
Binary Search code
A clean, runnable Binary Search implementation in Python, JavaScript, Java, C++, C, Pseudocode. Pick a language, copy the code, or open it pre-loaded in the Coddy Playground.
Binary Search code in Python
Python
1def binary_search(a, target):2 lo, hi = 0, len(a) - 13 while lo <= hi:4 mid = (lo + hi) // 25 if a[mid] == target:6 return mid7 if a[mid] < target:8 lo = mid + 1 # search the right half9 else:10 hi = mid - 1 # search the left half11 return -112
13
14nums = [1, 2, 3, 5, 7, 8, 9] # must be sorted15print("Index of 5:", binary_search(nums, 5))16print("Index of 4:", binary_search(nums, 4))Binary Search code in JavaScript
JavaScript
1function binarySearch(a, target) {2 let lo = 0;3 let hi = a.length - 1;4 while (lo <= hi) {5 const mid = Math.floor((lo + hi) / 2);6 if (a[mid] === target) return mid;7 if (a[mid] < target) {8 lo = mid + 1; // search the right half9 } else {10 hi = mid - 1; // search the left half11 }12 }13 return -1;14}15
16const nums = [1, 2, 3, 5, 7, 8, 9]; // must be sorted17console.log("Index of 5:", binarySearch(nums, 5));18console.log("Index of 4:", binarySearch(nums, 4));Binary Search code in Java
Java
1public class Main {2 static int binarySearch(int[] a, int target) {3 int lo = 0;4 int hi = a.length - 1;5 while (lo <= hi) {6 int mid = (lo + hi) / 2;7 if (a[mid] == target) return mid;8 if (a[mid] < target) {9 lo = mid + 1; // search the right half10 } else {11 hi = mid - 1; // search the left half12 }13 }14 return -1;15 }16
17 public static void main(String[] args) {18 int[] nums = {1, 2, 3, 5, 7, 8, 9}; // must be sorted19 System.out.println("Index of 5: " + binarySearch(nums, 5));20 System.out.println("Index of 4: " + binarySearch(nums, 4));21 }22}Binary Search code in C++
C++
1#include <iostream>2#include <vector>3
4int binarySearch(const std::vector<int>& a, int target) {5 int lo = 0;6 int hi = static_cast<int>(a.size()) - 1;7 while (lo <= hi) {8 int mid = lo + (hi - lo) / 2;9 if (a[mid] == target) return mid;10 if (a[mid] < target) {11 lo = mid + 1; // search the right half12 } else {13 hi = mid - 1; // search the left half14 }15 }16 return -1;17}18
19int main() {20 std::vector<int> nums = {1, 2, 3, 5, 7, 8, 9}; // must be sorted21 std::cout << "Index of 5: " << binarySearch(nums, 5) << "\n";22 std::cout << "Index of 4: " << binarySearch(nums, 4) << "\n";23 return 0;24}Binary Search code in C
C
1#include <stdio.h>2
3int binary_search(const int a[], int n, int target) {4 int lo = 0;5 int hi = n - 1;6 while (lo <= hi) {7 int mid = lo + (hi - lo) / 2;8 if (a[mid] == target) return mid;9 if (a[mid] < target) {10 lo = mid + 1; /* search the right half */11 } else {12 hi = mid - 1; /* search the left half */13 }14 }15 return -1;16}17
18int main(void) {19 int nums[] = {1, 2, 3, 5, 7, 8, 9}; /* must be sorted */20 int n = sizeof(nums) / sizeof(nums[0]);21 printf("Index of 5: %d\n", binary_search(nums, n, 5));22 printf("Index of 4: %d\n", binary_search(nums, n, 4));23 return 0;24}Binary Search code in Pseudocode
Pseudocode
1DECLARE nums : ARRAY[1:7] OF INTEGER2DECLARE n : INTEGER3n ← 74// The array must be sorted for binary search5nums[1] ← 16nums[2] ← 27nums[3] ← 38nums[4] ← 59nums[5] ← 710nums[6] ← 811nums[7] ← 912
13FUNCTION binarySearch(target : INTEGER) RETURNS INTEGER14 DECLARE lo : INTEGER15 DECLARE hi : INTEGER16 DECLARE mid : INTEGER17 lo ← 118 hi ← n19 WHILE lo <= hi DO20 mid ← (lo + hi) DIV 221 IF nums[mid] = target THEN22 RETURN mid23 ENDIF24 IF nums[mid] < target THEN25 // Target is larger — search the right half26 lo ← mid + 127 ELSE28 // Target is smaller — search the left half29 hi ← mid - 130 ENDIF31 ENDWHILE32 RETURN -133ENDFUNCTION34
35OUTPUT "Index of 5 is ", binarySearch(5)36OUTPUT "Index of 4 is ", binarySearch(4)Binary Search FAQ
What is the time complexity of binary search?
O(log n) in the average and worst case, because every comparison halves the remaining search window, and O(1) in the best case when the first middle element is the target. The iterative version uses O(1) extra space.Why does binary search require a sorted array?
The halving step relies on order: comparing the target with the middle element only tells you which half to discard if everything left of the middle is smaller and everything right of it is larger. On unsorted data that inference is invalid — use linear search instead, or sort first.
What is the difference between binary search and linear search?
Linear search scans elements one by one (
O(n)) and works on any array; binary search halves a sorted array's search window (O(log n)) but requires sorted input. For a handful of items the difference is negligible — at scale binary search wins decisively.How many comparisons does binary search need?
At most about
log2(n) + 1: 10 comparisons cover 1,000 elements, 20 comparisons cover 1,000,000. That logarithmic growth is what makes it the default lookup on sorted data.What is the classic overflow bug in binary search?
Computing the middle as
(lo + hi) / 2 can overflow fixed-size integers when lo + hi exceeds the type's maximum. The safe form is mid = lo + (hi - lo) / 2. In Python this doesn't matter (arbitrary-precision integers), but in Java/C/C++ it's a real, famous bug.Is binary search the same as a binary search tree?
They share the halving idea but differ in structure: binary search is an algorithm over a sorted array, while a binary search tree is a linked data structure that keeps its keys ordered so lookups descend left or right at each node.
Related resources
More visualizations
