1.
Lower Bound
public int lowerBound(int[] arr, int target) {
int low = 0, high = [Link];
while (low < high) {
int mid = low + (high - low) / 2;
if (arr[mid] < target)
low = mid + 1;
else
high = mid;
}
return low;
}
2. Upper Bound
public int upperBound(int[] arr, int target) {
int low = 0, high = [Link];
while (low < high) {
int mid = low + (high - low) / 2;
if (arr[mid] <= target)
low = mid + 1;
else
high = mid;
}
return low;
}
3. First and Last Occurrence
public int firstOccurrence(int[] arr, int target) {
int low = 0, high = [Link] - 1, ans = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
ans = mid;
high = mid - 1;
} else if (arr[mid] < target)
low = mid + 1;
else
high = mid - 1;
}
return ans;
}
public int lastOccurrence(int[] arr, int target) {
int low = 0, high = [Link] - 1, ans = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
ans = mid;
low = mid + 1;
} else if (arr[mid] < target)
low = mid + 1;
else
high = mid - 1;
}
return ans;
}
4. Insert Position
public int insertPosition(int[] arr, int target) {
int low = 0, high = [Link];
while (low < high) {
int mid = low + (high - low) / 2;
if (arr[mid] < target)
low = mid + 1;
else
high = mid;
}
return low;
}
5. Search in Rotated Sorted Array
public int searchRotated(int[] arr, int target) {
int low = 0, high = [Link] - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) return mid;
if (arr[low] <= arr[mid]) {
if (arr[low] <= target && target < arr[mid])
high = mid - 1;
else
low = mid + 1;
} else {
if (arr[mid] < target && target <= arr[high])
low = mid + 1;
else
high = mid - 1;
}
}
return -1;
}
6. Minimum in Rotated Sorted Array
public int findMin(int[] arr) {
int low = 0, high = [Link] - 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (arr[mid] > arr[high])
low = mid + 1;
else
high = mid;
}
return arr[low];
}
7. Rotation Count
public int countRotations(int[] arr) {
int low = 0, high = [Link] - 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (arr[mid] > arr[high])
low = mid + 1;
else
high = mid;
}
return low;
}
8. Peak Element
public int findPeak(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;
}
9. Square Root in Log(n)
public int sqrt(int x) {
int low = 0, high = x, ans = 0;
while (low <= high) {
int mid = low + (high - low) / 2;
if ((long)mid * mid <= x) {
ans = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return ans;
}
10. Koko Eating Bananas
public int minEatingSpeed(int[] piles, int h) {
int low = 1, high = (int)1e9, ans = high;
while (low <= high) {
int mid = low + (high - low) / 2;
int hours = 0;
for (int bananas : piles)
hours += (bananas + mid - 1) / mid;
if (hours <= h) {
ans = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
return ans;
}
11. Search in 2D Matrix
public boolean searchMatrix(int[][] matrix, int target) {
int rows = [Link], cols = matrix[0].length;
int low = 0, high = rows * cols - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
int val = matrix[mid / cols][mid % cols];
if (val == target)
return true;
else if (val < target)
low = mid + 1;
else
high = mid - 1;
}
return false;
}
12. Search in 2D Matrix II
public boolean searchMatrix2(int[][] matrix, int target) {
int row = 0, col = matrix[0].length - 1;
while (row < [Link] && col >= 0) {
if (matrix[row][col] == target)
return true;
else if (matrix[row][col] > target)
col--;
else
row++;
}
return false;
}