Binary Search
Searching O(log n) O(1)Halves a sorted range each step by comparing the middle element with the target.
3
7
9
15
23
28
34
41
Searching a sorted array of 8 for 15.
InvariantIf the target is present it lies in [0..7] — everything outside has been ruled out by order alone.
1/3
probes0lo0hi7mid0
binary-search.c
int binarySearch(int arr[], int n, int target) {int lo = 0, hi = n - 1;while (lo <= hi) {int mid = lo + (hi - lo) / 2;if (arr[mid] == target)return mid;if (arr[mid] < target)lo = mid + 1;elsehi = mid - 1;}return -1;}
How Binary Search works
Compare the target with the middle of a sorted range. One comparison discards half the remaining candidates; repeat on the surviving half until found or empty.
Best case
Target is exactly the middle: O(1).
Worst case
Halving until one element remains: O(log n).
When to use it
Any sorted array — also as the building block for lower/upper-bound lookups.