Searching Algorithms
BeginnerBinary search is not just for sorted arrays — master the template that solves dozens of "find the answer" problems.
Think of it this way
Think of guessing a secret number between 1 and 1000. A smart guesser asks "Is it more than 500?" — if yes, they only consider 501–1000 next. Each guess cuts the remaining options in half. That is binary search: you never check every number, you eliminate half the possibilities with every single step.
int[] arr = {1, 3, 5, 7, 9, 11, 13};
int target = 7;
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; // found!
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 foundOverview
Binary search is one of the most powerful and misunderstood algorithms. The classic form searches a sorted array in O(log n). But the real power is the generalized template: binary search on the answer. If you can define a monotonic function f(x) — where all values below x fail a condition and all values above pass — you can binary search for the boundary. This pattern solves problems about capacity, minimum/maximum feasibility, and more.
Time & Space Complexity
| Operation | Time | Space |
|---|---|---|
| Linear search | O(n) | O(1) |
| Binary search (sorted) | O(log n) | O(1) |
| Binary search recursive | O(log n) | O(log n) |
| Search in 2D matrix | O(log(m*n)) | O(1) |
| Ternary search (unimodal) | O(log n) | O(1) |
Java Implementation
public class BinarySearch {
// Classic binary search — returns index or -1
public static int search(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;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
// Find first occurrence (leftmost) — O(log n)
public static int firstOccurrence(int[] arr, int target) {
int left = 0, right = arr.length - 1, 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;
else right = mid - 1;
}
return result;
}
// Search in rotated sorted array — O(log n)
public static 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;
if (arr[left] <= arr[mid]) { // left half is sorted
if (arr[left] <= target && target < arr[mid]) right = mid - 1;
else left = mid + 1;
} else { // right half is sorted
if (arr[mid] < target && target <= arr[right]) left = mid + 1;
else right = mid - 1;
}
}
return -1;
}
// Binary search on answer: minimum capacity to ship packages in D days
public static int shipWithinDays(int[] weights, int days) {
int left = 0, right = 0;
for (int w : weights) { left = Math.max(left, w); right += w; }
while (left < right) {
int mid = left + (right - left) / 2;
if (canShip(weights, days, mid)) right = mid;
else left = mid + 1;
}
return left;
}
private static boolean canShip(int[] weights, int days, int capacity) {
int daysNeeded = 1, currentLoad = 0;
for (int w : weights) {
if (currentLoad + w > capacity) { daysNeeded++; currentLoad = 0; }
currentLoad += w;
}
return daysNeeded <= days;
}
}Key Points to Remember
- Always use mid = left + (right - left) / 2 to avoid integer overflow
// ✗ can overflow when left + right > Integer.MAX_VALUE int mid = (left + right) / 2; // ✓ safe — equivalent but never overflows int mid = left + (right - left) / 2; - Three templates: find exact value, find leftmost occurrence, find rightmost occurrence
// Find leftmost: when found, keep going left if (arr[mid] == target) { result = mid; right = mid - 1; } // Find rightmost: when found, keep going right if (arr[mid] == target) { result = mid; left = mid + 1; } - Binary search on answer: if you can define a monotonic yes/no function, you can binary search
// "Can we ship all packages within D days using capacity mid?" while (left < right) { int mid = left + (right - left) / 2; if (canDo(mid)) right = mid; // try smaller else left = mid + 1; // need larger } - Works on any monotonic condition, not just sorted arrays — the key is a clear yes/no boundary
- Rotated sorted array: one half is always sorted, use that to decide which half to search
if (arr[left] <= arr[mid]) { // left half is sorted if (arr[left] <= target && target < arr[mid]) right = mid - 1; else left = mid + 1; }
Interview Questions
Sign in to ask AriaSearch in a rotated sorted array
Find minimum in rotated sorted array
Koko eating bananas — binary search on answer
Find peak element
Median of two sorted arrays
Ask Aria about Searching Algorithms
Your personal AI tutor — ask anything about this concept