Binary Search¶
Definition¶
A divide-and-conquer search algorithm that repeatedly divides a SORTED array in half to locate the target.
Key Insight: Eliminates HALF of remaining elements each iteration: n -> n/2 -> n/4 -> ... -> 1 = log2(n) steps
Big O Complexity¶
When to Use¶
Pros and Cons¶
Implementation¶
Standard Binary Search¶
// Iterative - preferred (O(1) space)
public int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // Avoid overflow
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // Not found
}
Recursive Binary Search¶
public int binarySearchRecursive(int[] arr, int target, int left, int right) {
if (left > right) return -1;
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
return binarySearchRecursive(arr, target, mid + 1, right);
} else {
return binarySearchRecursive(arr, target, left, mid - 1);
}
}
Find First Occurrence¶
// Returns first index where arr[i] == target
public int findFirst(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;
} else {
right = mid - 1;
}
}
return result;
}
Find Last Occurrence¶
public int findLast(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;
} else {
right = mid - 1;
}
}
return result;
}
Lower Bound (First >= target)¶
// Returns first index where arr[i] >= target
public int lowerBound(int[] arr, int target) {
int left = 0, right = arr.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left; // Insertion point for target
}
Upper Bound (First > target)¶
// Returns first index where arr[i] > target
public int upperBound(int[] arr, int target) {
int left = 0, right = arr.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] <= target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
Rotated Sorted Array¶
Search in Rotated Array¶
// [4,5,6,7,0,1,2] - find target
public int searchRotated(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
// Determine which half is sorted
if (nums[left] <= nums[mid]) {
// Left half is sorted
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1; // Target in left half
} else {
left = mid + 1; // Target in right half
}
} else {
// Right half is sorted
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1; // Target in right half
} else {
right = mid - 1; // Target in left half
}
}
}
return -1;
}
Find Minimum in Rotated Array¶
public int findMin(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1; // Min is in right half
} else {
right = mid; // Min is in left half (including mid)
}
}
return nums[left];
}
Find Minimum with Duplicates¶
public int findMinWithDuplicates(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1;
} else if (nums[mid] < nums[right]) {
right = mid;
} else {
right--; // Can't determine, shrink
}
}
return nums[left];
}
Search in Rotated with Duplicates¶
public boolean searchRotatedWithDuplicates(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return true;
// Handle duplicates at boundaries
if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
left++;
right--;
} else if (nums[left] <= nums[mid]) {
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return false;
}
Common Patterns¶
Binary Search on Answer¶
// Find minimum k such that condition is satisfied
public int binarySearchOnAnswer(int low, int high) {
while (low < high) {
int mid = low + (high - low) / 2;
if (condition(mid)) {
high = mid; // Try smaller
} else {
low = mid + 1; // Need larger
}
}
return low;
}
Find Peak Element¶
public int findPeakElement(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[mid + 1]) {
right = mid; // Peak is at mid or left
} else {
left = mid + 1; // Peak is to the right
}
}
return left;
}
Square Root¶
public int sqrt(int x) {
if (x < 2) return x;
int left = 1, right = x / 2;
while (left <= right) {
int mid = left + (right - left) / 2;
long square = (long) mid * mid;
if (square == x) {
return mid;
} else if (square < x) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return right; // Floor of sqrt
}
First Bad Version¶
public int firstBadVersion(int n) {
int left = 1, right = n;
while (left < right) {
int mid = left + (right - left) / 2;
if (isBadVersion(mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
Koko Eating Bananas¶
// Find minimum speed to eat all bananas in h hours
public int minEatingSpeed(int[] piles, int h) {
int left = 1;
int right = Arrays.stream(piles).max().getAsInt();
while (left < right) {
int mid = left + (right - left) / 2;
if (canFinish(piles, mid, h)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
private boolean canFinish(int[] piles, int speed, int h) {
int hours = 0;
for (int pile : piles) {
hours += (pile + speed - 1) / speed; // Ceiling division
}
return hours <= h;
}
Search in 2D Matrix¶
// Rows and columns sorted
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length, n = matrix[0].length;
int left = 0, right = m * n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
int value = matrix[mid / n][mid % n];
if (value == target) {
return true;
} else if (value < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return false;
}
Find First and Last Position¶
public int[] searchRange(int[] nums, int target) {
int first = findFirst(nums, target);
if (first == -1) return new int[]{-1, -1};
int last = findLast(nums, target);
return new int[]{first, last};
}
Java Built-in Methods¶
// Arrays.binarySearch
int[] arr = {1, 3, 5, 7, 9};
int index = Arrays.binarySearch(arr, 5); // Returns 2
// If not found, returns -(insertion point) - 1
int notFound = Arrays.binarySearch(arr, 4); // Returns -3
// To get insertion point: -notFound - 1 = 2
// Collections.binarySearch
List<Integer> list = Arrays.asList(1, 3, 5, 7, 9);
int idx = Collections.binarySearch(list, 5); // Returns 2
// With custom comparator
Integer[] arr2 = {9, 7, 5, 3, 1}; // Descending
int idx2 = Arrays.binarySearch(arr2, 5, Collections.reverseOrder());
Tips & Tricks¶
