Binary Search Basics

Ordering makes the search faster

Imagine a sorted array. If the middle value is smaller than the target, then every element to the left of the middle is also unsuitable: none of them can be larger than the value we just checked. So the left half no longer needs to be considered. If the middle value is larger than the target, the right part can be discarded in the same way.

int[] values = {2, 5, 8, 12, 16, 23, 31};
int target = 16;

int left = 0;
int right = values.length - 1;

The range [left, right] stores the positions where the answer may still be. Each midpoint check either finds the target immediately or significantly narrows this range.

Why the complexity is O(log n)

After every step, the search area is roughly halved: n, then n / 2, n / 4, n / 8, and so on. The number of halvings required to reach one element grows as log n, so binary search runs in O(log n) time.

What must be true

You cannot take an arbitrary array and start moving boundaries based on its midpoint. The algorithm needs a property that lets you determine, after checking the midpoint, which part of the search space can safely be discarded. In classic binary search, that property is the array's sorted order.