Binary Search is an efficient searching algorithm used to find an element in a sorted array or sorted list. Instead of checking every element one by one, it repeatedly cuts the search space into two halves.
Because half of the remaining elements are discarded at every step, binary search is much faster than linear search for large sorted data sets.
The strength of binary search comes from elimination. After one comparison, half of the remaining elements are ignored. After another comparison, half of what remains is ignored again.
For example, if an array has 1,024 elements:
That is why binary search has logarithmic time complexity.
Binary search works correctly only when the data is sorted.
At each step:
This is a classic divide and conquer algorithm because each step reduces the problem from size n to roughly n / 2.
low = 0 and high = n - 1.low <= high, compute the middle index.arr[mid] == target, return mid.arr[mid] < target, move to the right half by setting low = mid + 1.arr[mid] > target, move to the left half by setting high = mid - 1.-1.| Case | Complexity | Reason |
|---|---|---|
| Best case | O(1) | Target is found at the first middle check |
| Average case | O(log n) | Search space is halved repeatedly |
| Worst case | O(log n) | Need to reduce the interval until empty |
| Iterative space | O(1) | Uses only a few variables |
| Recursive space | O(log n) | Uses call stack for recursive calls |
The iterative version is usually preferred because it is simple and uses constant extra space.
public class BinarySearchIterative {
static int binarySearch(int[] arr, int target) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
return mid;
}
if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
}The recursive version expresses the divide-and-conquer idea more directly, but it uses extra stack space.
public class BinarySearchRecursive {
static int binarySearch(int[] arr, int low, int high, int target) {
if (low > high) {
return -1;
}
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
return mid;
}
if (arr[mid] < target) {
return binarySearch(arr, mid + 1, high, target);
}
return binarySearch(arr, low, mid - 1, target);
}
}Instead of writing (low + high) / 2, many implementations use:
mid = low + (high - low) / 2
This avoids possible integer overflow when low + high becomes too large.
When solving binary search questions by hand, follow this order:
low and high.mid.arr[mid] with the target.Suppose:
arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19} and target = 7
| Step | low | high | mid | arr[mid] | Decision |
|---|---|---|---|---|---|
| 1 | 0 | 9 | 4 | 9 | Search left half |
| 2 | 0 | 3 | 1 | 3 | Search right half |
| 3 | 2 | 3 | 2 | 5 | Search right half |
| 4 | 3 | 3 | 3 | 7 | Found |
Binary search ends when low becomes greater than high. This means there is no valid search interval left, so the target does not exist in the array.
This stopping condition is very important. Without it, the loop or recursion may continue incorrectly.
Binary search is not limited to exact search. Many common interview and algorithm problems are based on its variants.
| Variant | Goal | Main Idea |
|---|---|---|
| First occurrence | Find the leftmost index of target | When found, continue searching left |
| Last occurrence | Find the rightmost index of target | When found, continue searching right |
| Count occurrences | Count duplicates | Use first and last occurrence |
| Floor | Largest value less than or equal to target | Track best smaller value |
| Ceiling | Smallest value greater than or equal to target | Track best larger value |
| Rotated sorted array search | Find value in rotated array | Identify which half is sorted |
| Binary search on answer | Search over possible answers | Use a monotonic condition |
When duplicates are present, normal binary search may return any matching index. To find the first or last occurrence, continue the search even after a match is found.
public class BinarySearchOccurrences {
static int firstOccurrence(int[] arr, int target) {
int low = 0;
int high = arr.length - 1;
int result = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
result = mid;
high = mid - 1;
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return result;
}
static int lastOccurrence(int[] arr, int target) {
int low = 0;
int high = arr.length - 1;
int result = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
result = mid;
low = mid + 1;
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return result;
}
}Sometimes we do not search for an array element at all. Instead, we search over a range of possible answers. This works when the condition is monotonic, meaning that once a certain value works, all larger values also work, or all smaller values also work.
public class SqrtBinarySearch {
static long sqrt(long n) {
if (n < 2) {
return n;
}
long low = 1;
long high = n / 2;
long result = 1;
while (low <= high) {
long mid = low + (high - low) / 2;
if (mid * mid == n) {
return mid;
}
if (mid * mid < n) {
result = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return result;
}
}| Aspect | Binary Search | Linear Search |
|---|---|---|
| Data requirement | Needs sorted data | Works on any data |
| Time complexity | O(log n) | O(n) |
| Best use case | Large sorted collections | Small or unsorted collections |
| Implementation | Slightly more careful | Very simple |
(low + high) / 2 carelessly in languages where overflow matters.Explore 500+ free tutorials across 20+ languages and frameworks.