Binary Search – Java Solutions with Examples &
Complexity
====================================================
BINARY SEARCH PROBLEMS – JAVA (Brute + Optimal)
====================================================
1) Peak Index in Mountain Array
--------------------------------
Example:
Input: [1,3,5,7,6,4,2]
Output: 3 (7 is peak)
Brute Force:
Time Complexity: O(n)
Space Complexity: O(1)
Optimal (Binary Search):
Time Complexity: O(log n)
Space Complexity: O(1)
public static int peakIndex(int[] arr) {
int low = 0, high = [Link] - 1;
while(low < high) {
int mid = low + (high - low)/2;
if(arr[mid] < arr[mid+1]) low = mid + 1;
else high = mid;
}
return low;
}
2) Search in Rotated Sorted Array
---------------------------------
Example:
Input: [4,5,6,7,0,1,2], target = 0
Output: 4
Brute Force:
Time Complexity: O(n)
Space Complexity: O(1)
Optimal:
Time Complexity: O(log n)
Space Complexity: O(1)
public static int search(int[] nums, int target) {
int low = 0, high = [Link] - 1;
while(low <= high) {
int mid = low + (high - low)/2;
if(nums[mid] == target) return mid;
if(nums[low] <= nums[mid]) {
if(target >= nums[low] && target < nums[mid])
high = mid - 1;
else low = mid + 1;
} else {
if(target > nums[mid] && target <= nums[high])
low = mid + 1;
else high = mid - 1;
}
}
return -1;
}
3) Single Element in Sorted Array
---------------------------------
Example:
Input: [1,1,2,2,3,4,4]
Output: 3
Brute Force:
Time Complexity: O(n)
Space Complexity: O(1)
Optimal:
Time Complexity: O(log n)
Space Complexity: O(1)
public static int singleNonDuplicate(int[] nums) {
int low = 0, high = [Link] - 1;
while(low < high) {
int mid = low + (high - low)/2;
if(mid % 2 == 1) mid--;
if(nums[mid] == nums[mid+1])
low = mid + 2;
else high = mid;
}
return nums[low];
}
4) Aggressive Cows
------------------
Example:
Stalls: [1,2,4,8,9], cows = 3
Output: 3
Optimal (Binary Search on Answer):
Time Complexity: O(n log(maxDistance))
Space Complexity: O(1)
5) Allocate Minimum Pages
-------------------------
Example:
Books: [12,34,67,90], Students = 2
Output: 113
Brute Force: O(n * sumPages)
Optimal: O(n log(sumPages))
Space: O(1)
6) Painter’s Partition
----------------------
Example:
Boards: [10,20,30,40], Painters = 2
Output: 60
Optimal:
Time Complexity: O(n log(totalLength))
Space Complexity: O(1)
7) Median of 2 Sorted Arrays
----------------------------
Example:
A = [1,3], B = [2]
Output: 2.0
Brute Force: O(n + m)
Optimal: O(log(min(n,m)))
Space: O(1)
public static double findMedian(int[] A, int[] B) {
if([Link] > [Link]) return findMedian(B, A);
int n = [Link], m = [Link];
int low = 0, high = n;
while(low <= high) {
int cut1 = (low + high)/2;
int cut2 = (n + m + 1)/2 - cut1;
int left1 = (cut1 == 0) ? Integer.MIN_VALUE : A[cut1-1];
int left2 = (cut2 == 0) ? Integer.MIN_VALUE : B[cut2-1];
int right1 = (cut1 == n) ? Integer.MAX_VALUE : A[cut1];
int right2 = (cut2 == m) ? Integer.MAX_VALUE : B[cut2];
if(left1 <= right2 && left2 <= right1) {
if((n+m)%2 == 0)
return ([Link](left1,left2)+[Link](right1,right2))/2.0;
else return [Link](left1,left2);
}
else if(left1 > right2) high = cut1 - 1;
else low = cut1 + 1;
}
return 0.0;
}