Binary search is more than just searching a sorted array. It's a thinking pattern that applies to a huge range of problems.
Binary search finds a target in a sorted array by repeatedly halving the search space. Each step eliminates half the remaining elements.
Array: [1, 3, 5, 7, 9, 11, 13]
Target: 7
Step 1: mid = 5 → 7 > 5 → search right half
Step 2: mid = 9 → 7 < 9 → search left half
Step 3: mid = 7 → found!
Time: O(log n) — 1 billion elements needs only ~30 comparisons.
public int binarySearch(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // avoids integer overflow
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1; // target is in right half
} else {
right = mid - 1; // target is in left half
}
}
return -1; // not found
}public int firstOccurrence(int[] arr, int target) {
int left = 0, right = arr.length - 1;
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
result = mid;
right = mid - 1; // keep searching left
} else if (arr[mid] < target) {
left = mid + 1;
}
public int lastOccurrence(int[] arr, int target) {
int left = 0, right = arr.length - 1;
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
result = mid;
left = mid + 1; // keep searching right
} else if (arr[mid] < target) {
left = mid + 1;
}
This is the most powerful pattern — binary search on a value range, not an array index.
public int shipWithinDays(int[] weights, int days) {
// Binary search on capacity (answer range)
int left = 0, right = 0;
for (int w : weights) {
left = Math.max(left, w); // minimum possible capacity
right += w; // maximum possible capacity
}
while (left < right) {
int mid = left + (right - left) / 2;
if (canShip(weights, days, mid)) {
right = mid; // try smaller capacity
} else {
left =
public int searchRotated(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
}
// Left half is sorted
if (arr[left] <= arr[mid]) {
if (arr[left] <= target && target < arr[mid]) {
right = mid - 1;
} else {
left
Ask yourself: "Is there a monotonic condition I can binary search on?"
| Problem type | Binary search on |
|---|---|
| Find element in sorted array | Index |
| Find minimum valid value | Answer range |
| Find first/last occurrence | Index with boundary tracking |
| Minimize maximum / Maximize minimum | Answer range |
| Kth smallest/largest | Value range |
mid = left + (right - left) / 2 to avoid overflow