Let's play a small game. I am thinking of a number between 1 and 100. Every time you guess, I will tell you whether my number is higher or lower.
You could guess 1, 2, 3, 4... one by one. That is linear search, and in the worst case it takes 100 guesses.
But a smart player starts with 50.
Guess 50 → "Higher" → the number is in 51..100
Guess 75 → "Lower" → the number is in 51..74
Guess 62 → "Higher" → the number is in 63..74
...Every guess throws away half of the remaining numbers. With this strategy you will always find the number in at most 7 guesses.
That strategy is Binary Search, one of the most important algorithms in all of DSA.
In the previous chapter, we saw that linear search checks elements one by one and takes O(n) time. Binary search uses one extra piece of information, that the data is sorted, to bring that down to O(log n).
What is Binary Search?
Binary Search is a searching algorithm for sorted data that repeatedly compares the target with the middle element and discards the half in which the target cannot be present.
The word binary means "two". At every step, the search space is split into two halves, and we keep only one of them.
At every step there are only three possibilities:
middle == target → Found
middle < target → Target can only be on the RIGHT side
middle > target → Target can only be on the LEFT sideThe One Rule: Data Must Be Sorted
Binary search only works because the data is in order.
Look at this sorted array:
[3, 8, 15, 23, 42, 56, 71, 89]If the middle element is 23 and we are looking for 56, we know for sure that 56 cannot be on the left, because everything on the left is smaller than 23.
Now look at an unsorted array:
[42, 3, 89, 15, 56, 8, 71, 23]If the middle is 15, it tells us nothing. 56 could be on either side. Throwing away half the array could throw away the answer.
Binary search on unsorted data can silently give wrong answers. Always make sure the data is sorted first.
How Binary Search Works
We keep two pointers:
low→ the start of the current search rangehigh→ the end of the current search range
and compute the middle:
mid = (low + high) / 2 (we will improve this formula soon)Example 1: Searching for 56
Index: 0 1 2 3 4 5 6 7
Value: 3 8 15 23 42 56 71 89Step 1
low = 0, high = 7
mid = (0 + 7) / 2 = 3 → arr[3] = 23
23 < 56 → target is on the right
low = mid + 1 = 4Index: 0 1 2 3 | 4 5 6 7
✗ ✗ ✗ ✗ | 42 56 71 89Step 2
low = 4, high = 7
mid = (4 + 7) / 2 = 5 → arr[5] = 56
56 == 56 → Found at index 5We found the element in just 2 comparisons. Linear search would have needed 6.
Example 2: Searching for 20 (Not Present)
low=0, high=7 → mid=3 → arr[3]=23 → 23 > 20 → high = 2
low=0, high=2 → mid=1 → arr[1]=8 → 8 < 20 → low = 2
low=2, high=2 → mid=2 → arr[2]=15 → 15 < 20 → low = 3
low=3, high=2 → low > high → stop → return -1When low becomes greater than high, the search range is empty. The target is not in the array.
Notice that we use mid + 1 and mid - 1, not mid. We have already checked arr[mid], so there is no reason to keep it in the range.
Iterative Binary Search in Java
class Main {
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; // found
} else if (arr[mid] < target) {
low = mid + 1; // search the right half
} else {
high = mid - 1; // search the left half
}
}
return -1; // not found
}
public static void main(String[] args) {
int[] arr = {3, 8, 15, 23, 42, 56, 71, 89};
System.out.println("Index of 56: " + binarySearch(arr, 56));
System.out.println("Index of 3: " + binarySearch(arr, 3));
System.out.println("Index of 89: " + binarySearch(arr, 89));
System.out.println("Index of 20: " + binarySearch(arr, 20));
}
}Output:
Index of 56: 5
Index of 3: 0
Index of 89: 7
Index of 20: -1Pay attention to the loop condition: low <= high. When low == high, there is still one element left to check. Using low < high here would skip it.
Why low + (high - low) / 2?
The simple formula (low + high) / 2 has a hidden bug.
In Java, an int can hold values only up to 2,147,483,647. If low and high are both large, their sum can go beyond that limit and overflow into a negative number.
int low = 1_500_000_000;
int high = 2_000_000_000;
System.out.println("(low + high) / 2 = " + (low + high) / 2);
System.out.println("low + (high - low) / 2 = " + (low + (high - low) / 2));Output:
(low + high) / 2 = -397483648
low + (high - low) / 2 = 1750000000A negative mid would crash the program with an ArrayIndexOutOfBoundsException.
The formula low + (high - low) / 2 gives the same middle, but high - low never overflows when both are valid indexes. This exact bug existed in Java's own Arrays.binarySearch for years before it was fixed in 2006, so interviewers love asking about it.
Recursive Binary Search
Binary search also has a natural recursive form (see the Recursion chapter). Each call works on a smaller range.
static int binarySearch(int[] arr, int target, int low, int high) {
if (low > high) {
return -1; // base case: empty range
}
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
return binarySearch(arr, target, mid + 1, high);
} else {
return binarySearch(arr, target, low, mid - 1);
}
}Calling it:
int[] arr = {3, 8, 15, 23, 42, 56, 71, 89};
System.out.println(binarySearch(arr, 71, 0, arr.length - 1));
System.out.println(binarySearch(arr, 10, 0, arr.length - 1));Output:
6
-1The recursive version uses O(log n) stack space. The iterative version uses O(1), so it is usually preferred.
Time and Space Complexity
Each step cuts the search space in half:
n → n/2 → n/4 → n/8 → ... → 1How many times can we halve n before only one element is left? About log₂ n times. (We saw this pattern in the Time Complexity chapter when we discussed O(log n).)
More precisely, binary search makes at most ⌊log₂ n⌋ + 1 comparisons with the middle element.
Number of elements (n) | Linear search (worst) | Binary search (worst) |
|---|---|---|
100 | 100 | 7 |
1,000 | 1,000 | 10 |
1,000,000 | 1,000,000 | 20 |
1,000,000,000 | 1,000,000,000 | 30 |
Searching one billion sorted numbers in just 30 steps — that is the power of O(log n).
Case | Time |
|---|---|
Best (target is the first middle) | O(1) |
Average | O(log n) |
Worst | O(log n) |
Space (iterative) | O(1) |
Space (recursive) | O(log n) |
Binary search needs random access (jumping straight to the middle in O(1)). That is why it works on arrays but not efficiently on linked lists, where reaching the middle takes O(n).
Binary Search with Duplicates
What if the target appears more than once?
Index: 0 1 2 3 4 5 6 7
Value: 2 4 4 4 7 9 9 12The basic binary search will return some index of 4, but not necessarily the first or the last one. Many problems need a specific one, so we use small variations.
First Occurrence
When we find the target, we save the index and keep searching on the left, in case there is an earlier copy:
static int firstOccurrence(int[] arr, int target) {
int low = 0, high = arr.length - 1;
int answer = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
answer = mid; // record it...
high = mid - 1; // ...but keep looking on the left
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return answer;
}Last Occurrence
Same idea, but after a match we keep searching on the right: replace high = mid - 1 with low = mid + 1 in the match branch.
Counting Occurrences in O(log n)
count = lastOccurrence - firstOccurrence + 1 (if the target exists)For the array above: 3 - 1 + 1 = 3 copies of 4.
Lower Bound and Upper Bound
These two variations are used everywhere in competitive programming and interviews.
Lower bound → the first index where
arr[i] >= targetUpper bound → the first index where
arr[i] > target
Index: 0 1 2 3 4 5 6 7
Value: 2 4 4 4 7 9 9 12
lower bound of 9 → index 5 (first value >= 9)
upper bound of 9 → index 7 (first value > 9)A very useful property: if the target is not present, the lower bound is exactly the position where it should be inserted to keep the array sorted. This is the classic Search Insert Position problem.
Complete Example: Binary Search Variations
import java.util.Arrays;
class Main {
// First index where arr[i] == target, or -1
static int firstOccurrence(int[] arr, int target) {
int low = 0, high = arr.length - 1;
int answer = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
answer = mid; // record it...
high = mid - 1; // ...but keep looking on the left
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return answer;
}
// Last index where arr[i] == target, or -1
static int lastOccurrence(int[] arr, int target) {
int low = 0, high = arr.length - 1;
int answer = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
answer = mid; // record it...
low = mid + 1; // ...but keep looking on the right
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return answer;
}
// Lower bound: first index where arr[i] >= target
// (returns arr.length if every element is smaller)
static int lowerBound(int[] arr, int target) {
int low = 0, high = arr.length - 1;
int answer = arr.length;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] >= target) {
answer = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
return answer;
}
// Upper bound: first index where arr[i] > target
static int upperBound(int[] arr, int target) {
int low = 0, high = arr.length - 1;
int answer = arr.length;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] > target) {
answer = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
return answer;
}
public static void main(String[] args) {
int[] arr = {2, 4, 4, 4, 7, 9, 9, 12};
System.out.println("Array: " + Arrays.toString(arr));
System.out.println("First 4: " + firstOccurrence(arr, 4));
System.out.println("Last 4: " + lastOccurrence(arr, 4));
int first = firstOccurrence(arr, 4);
int count = (first == -1) ? 0 : lastOccurrence(arr, 4) - first + 1;
System.out.println("Count of 4: " + count);
System.out.println("Lower bound of 9: " + lowerBound(arr, 9));
System.out.println("Upper bound of 9: " + upperBound(arr, 9));
System.out.println("Insert position of 8: " + lowerBound(arr, 8));
System.out.println("Insert position of 20: " + lowerBound(arr, 20));
}
}Output:
Array: [2, 4, 4, 4, 7, 9, 9, 12]
First 4: 1
Last 4: 3
Count of 4: 3
Lower bound of 9: 5
Upper bound of 9: 7
Insert position of 8: 5
Insert position of 20: 8Notice that upperBound - lowerBound also gives the count: for 9, 7 - 5 = 2.
Binary Search on the Answer
Binary search is not only for finding an element in an array. It can search over a range of possible answers.
The pattern works whenever the answers look like this:
possible answers: 0 1 2 3 4 5 6 7 8 ...
condition true? ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✗ ✗ ...
↑
we want the last ✓Once the condition becomes false, it stays false. That "sorted" true/false pattern is all binary search needs.
Example: Integer Square Root
Find the largest integer x such that x * x <= n, without using Math.sqrt().
static int floorSqrt(int n) {
int low = 0, high = n;
int answer = 0;
while (low <= high) {
int mid = low + (high - low) / 2;
if ((long) mid * mid <= n) { // long avoids overflow
answer = mid; // mid works, try bigger
low = mid + 1;
} else {
high = mid - 1; // mid too big
}
}
return answer;
}The cast to long matters: for a large mid, mid * mid would overflow an int.
This "binary search on answer" idea solves many famous interview problems, such as Koko Eating Bananas, Capacity to Ship Packages, Aggressive Cows and Book Allocation.
Search in a Rotated Sorted Array
A sorted array is sometimes "rotated" at an unknown point:
Original: [10, 20, 30, 40, 50, 60]
Rotated: [40, 50, 60, 10, 20, 30]The whole array is no longer sorted, but there is a key observation:
When you split a rotated sorted array at the middle, at least one half is always sorted.
So at each step we check which half is sorted, then check whether the target lies inside that sorted half's range. If it does, we go there; otherwise we go to the other half.
static int searchRotated(int[] arr, int target) {
int low = 0, high = arr.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
return mid;
}
if (arr[low] <= arr[mid]) { // left half is sorted
if (target >= arr[low] && target < arr[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
} else { // right half is sorted
if (target > arr[mid] && target <= arr[high]) {
low = mid + 1;
} else {
high = mid - 1;
}
}
}
return -1;
}Tracing a search for 20 in [40, 50, 60, 10, 20, 30]:
low=0, high=5 → mid=2 → arr[2]=60
left half [40, 50, 60] is sorted, 20 is not in 40..60 → low = 3
low=3, high=5 → mid=4 → arr[4]=20 → Found at index 4This version assumes all elements are distinct. It still runs in O(log n).
Java's Built-in Binary Search
Java already provides binary search:
// needs: import java.util.Arrays; at the top of the file
int[] arr = {3, 8, 15, 23, 42, 56, 71, 89};
System.out.println("Arrays.binarySearch(arr, 42) = " + Arrays.binarySearch(arr, 42));
System.out.println("Arrays.binarySearch(arr, 20) = " + Arrays.binarySearch(arr, 20));Output:
Arrays.binarySearch(arr, 42) = 4
Arrays.binarySearch(arr, 20) = -4Why -4? When the key is not found, Java returns -(insertionPoint) - 1. Here 20 would be inserted at index 3, so the result is -3 - 1 = -4. This guarantees that the result is negative only when the key is missing.
Two things to remember about Arrays.binarySearch (and Collections.binarySearch for lists):
The array must be sorted, otherwise the result is undefined.
If there are duplicates, there is no guarantee which copy's index is returned. Use your own first/last occurrence code when that matters.
Common Mistakes
1. Using Binary Search on Unsorted Data
It will not throw an error. It can just quietly give wrong answers. Always check that the input is sorted.
2. Wrong Loop Condition
With the low = mid + 1 / high = mid - 1 style used in this chapter, the condition must be while (low <= high). Using < misses the case where one element is left.
3. Infinite Loops from low = mid
// WRONG
low = mid; // if low == mid, the range never shrinksSuppose low = 4 and high = 5. Then mid = 4. If we set low = mid, low stays 4 forever. Always move past mid once it has been checked.
4. Integer Overflow
Use low + (high - low) / 2 for mid, and use long when multiplying in "binary search on answer" problems.
5. Using It on a Linked List
Binary search needs O(1) access to the middle element. On a linked list, reaching the middle costs O(n), which destroys the benefit.
Linear Search vs Binary Search
Feature | Linear Search | Binary Search |
|---|---|---|
Data must be sorted? | No | Yes |
Worst-case time | O(n) | O(log n) |
Best-case time | O(1) | O(1) |
Extra space | O(1) | O(1) iterative |
Works on linked lists? | Yes | Not efficiently |
Best for | Small or unsorted data, one-time searches | Large sorted data, repeated searches |
If your data is unsorted and you need to search it many times, it can be worth sorting it once (sorting is the topic of the next chapter) and then using binary search for every query.
Interview Tips and Practice Problems
Whenever you see any of these clues in a problem, think of binary search:
The input array is sorted (or rotated sorted)
The problem asks for
O(log n)timeYou need the minimum or maximum value that satisfies some condition
The answer lies in a numeric range and you can quickly check whether a guess works
Practice problems, roughly from easy to hard:
Binary Search (basic)
Search Insert Position
First and Last Position of Element in Sorted Array
Sqrt(x)
Find Peak Element
Search in Rotated Sorted Array
Find Minimum in Rotated Sorted Array
Koko Eating Bananas
Search a 2D Matrix
Median of Two Sorted Arrays (hard)
A tip for interviews: before writing code, say out loud what low, high and answer mean, and when the loop stops. Most binary search bugs come from being unclear about these boundaries.
The Main Idea
Binary Search finds an element in sorted data by checking the middle and discarding half of the remaining elements every time.
low = 0, high = n - 1
↓
while low <= high
↓
mid = low + (high - low) / 2
↓
arr[mid] == target → return mid
arr[mid] < target → low = mid + 1
arr[mid] > target → high = mid - 1
↓
return -1The facts to remember:
Requirement → sorted data with random access
Time → O(log n)
Space → O(1) iterative, O(log n) recursive
Variations → first/last occurrence, lower/upper bound,
binary search on answer, rotated arraysBinary search turns a search over a billion elements into about 30 steps — but only because the data is sorted. That is one big reason sorting is so important, and it is exactly what we study next.