Why does binary search require a sorted array?

AlgorithmsJunior~3 min read

Short answer

Binary search requires a sorted array because the decision to "go left or right" after comparing with the middle correctly splits the array into two parts only when there is a global order among the elements. When the data is ordered, one half is guaranteed not to contain the target value, so it can be discarded. In an unsorted array there is no such guarantee, and the algorithm can discard the half that holds the answer.

Detailed breakdown

Why order is needed

The halving idea: we take the middle, compare it with the target x, and decide which half to continue in. This decision relies on the fact that all elements to the left are no greater than the middle (or no less, depending on the order), and all elements to the right are the opposite.
Correctness invariant: at each step the set of candidates remains an interval of indices inside which the elements are ordered. Comparing with the middle guarantees that one of the halves cannot contain the answer, so it is safe to discard it.
Monotonicity of the predicate: classic binary search is equivalent to finding the boundary of a monotonic predicate P(i). For example, P(i) := a[i] ≥ x on an ascending array is monotonic in i. On an unsorted array P(i) jumps around (is not monotonic), and the boundary cannot be found correctly.
Not just speed, but correctness: without order the algorithm does not simply get slower - it can return the wrong answer (or "not found", even though the element is there).

Key invariant: if the array is sorted by a comparator cmp, then for any mid it holds that all i < mid are no greater than a[mid] (in cmp order), and all i > mid are no less than a[mid]. This is exactly what lets us discard a half.

How binary search works (briefly, step by step)

Maintain the bounds [l, r] of the target index.
Take mid = ⌊(l + r) / 2⌋.
Compare a[mid] with x.
If a[mid] < x (for ascending order), the answer cannot be on the left, so shift l = mid + 1; otherwise r = mid - 1.
Repeat until the interval narrows to empty or the element is found.

Simple code example (JS)

function binarySearch(arr, x) {
  // Requires: arr is sorted in ascending order
  let l = 0;
  let r = arr.length - 1;
  while (l <= r) {
    const mid = l + ((r - l) >> 1); // avoids overflow
    if (arr[mid] === x) return mid;
    if (arr[mid] < x) l = mid + 1;
    else r = mid - 1;
  }
  return -1; // not found
}

console.log(binarySearch([1, 3, 4, 7, 9, 12], 7)); // 3
console.log(binarySearch([1, 3, 4, 7, 9, 12], 8)); // -1

What breaks on an unsorted array

On unsorted data, the decision of "where to go" can discard the needed half:

const arr = [2, 9, 4, 7, 5];
const x = 5;
// l=0, r=4, mid=2 -> arr[2]=4. x>4 => go right (l=3)
// l=3, r=4, mid=3 -> arr[3]=7. x<7 => go left (r=2)
// Now l=3, r=2 => the loop ends, we return -1, even though 5 is there (index=4)
// The error comes from the lack of a global order: comparing with the middle does not guarantee there is no answer on the left/right.

Duplicates, the comparator, and requirements on order

Duplicates are allowed. You need to define the goal: any index of the element, the first one (lower_bound), or the last one (upper_bound).
The order must be total and transitive under the same comparator that the array was sorted by and that the search comparisons use. An inconsistent comparator breaks the invariants.
Special values (for example, NaN) break comparability: they need to be handled separately or excluded.

Generalization via a monotonic predicate (lower_bound)

Binary search actually looks for the boundary where the predicate P(i) changes from false to true. In an array sorted in ascending order, the predicate P(i): a[i] ≥ x is monotonic, so we can find the first index where the element is no less than x (lower_bound).

function lowerBound(arr, x) {
  // Returns the minimum index i such that arr[i] >= x.
  // If there is no such index, returns arr.length.
  let l = 0, r = arr.length; // half-open interval [l, r)
  while (l < r) {
    const mid = l + ((r - l) >> 1);
    if (arr[mid] >= x) r = mid; // true zone
    else l = mid + 1;           // false zone
  }
  return l;
}

const a = [1, 3, 3, 5, 8];
console.log(lowerBound(a, 3)); // 1 (first index with 3)
console.log(lowerBound(a, 4)); // 3 (first index with >=4 - that is 5)
console.log(lowerBound(a, 9)); // 5 (there are no such elements)

Practical takeaways and complexities

If you need a single search over unsorted data, use a linear pass, O(n).
If there are many searches, it pays to sort once at O(n log n) and then run O(log n) per query.
For dynamic data, maintain a structure with order (for example, a sorted array with binary search and insertions via binary search plus splicing, or a tree/index), so that the monotonicity binary search needs is preserved.
Binary search is not limited to arrays: it works on any ordered domain of values/answers where there is a monotonic criterion of reachability/feasibility.

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.