Modified Binary Search
The modified binary search pattern builds upon the basic binary search algorithm discussed above. It involves adapting the traditional binary search approach by applying certain conditions or transformations, allowing us to solve problems in which input data are modified in a certain way.
**A few common variations of the modified binary search pattern are:
**Binary search on a modified array: **Sometimes, the array may be modified in a certain way, which affects the search process. For example, the array might be sorted and then rotated around some unknown pivot. Alternatively, some elements in a sorted array might be modified based on a specific condition. To handle such scenarios, we can modify the basic binary search technique to detect anomalies in the sorted order.
** Binary search with multiple requirements:** When searching for a target satisfying multiple requirements, a modified binary search can be used. It involves adapting the comparison logic within the binary search to accommodate multiple specifications. Examples include** finding a target range rather than a single target or finding the leftmost or the rightmost occurrence of a target value**.
Min Max Distance: canHandle(D)=stations_needed(D) <= k → right=D (minimize D ✓)
Max Sweetness: canHandle(S)=pieces(S) >= k+1 → left=S+1 (maximize S ✓)
K Weakest: canHandle(X)=weakest_k_sum(X) <= threshold → right=X
int left = MIN, right = MAX;
while (left <= right) {
int mid = left + (right - left) / 2;
if (canHandle(mid)) {
left = mid + 1; // Try larger
} else {
right = mid - 1; // Must smaller
}
}
return right; // Answer is right (last valid)
double left = MIN, right = MAX;
while (right - left > 1e-6) {
double mid = (left + right) / 2;
if (canHandle(mid)) left = mid; // Push left up
else right = mid;
}
return left;
// Returns index of first > target (count <= target)
int upperBound(int[] arr, int target) {
int l = 0, r = arr.length;
while (l < r) {
int m = (l + r) / 2;
if (arr[m] <= target) l = m + 1;
else r = m;
}
return l;
}
// Returns index of first >= target
int lowerBound(int[] arr, int target) {
int l = 0, r = arr.length;
while (l < r) {
int m = (l + r) / 2;
if (arr[m] < target) l = m + 1;
else r = m;
}
return l;
}Search in Rotated Sorted Array
You may notice that at least one half of the array is always sorted—if the array is rotated by less than half the length of the array, at least the second half of the array will still be sorted. Contrarily, if the array is rotated by more than half the length of the array, then at least the first half of the array will be sorted. We can use this property to our advantage and modify the binarySearch function as follows:
public static int binarySearchRotated(int[] nums, int target) {
int low = 0;
int high = nums.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (nums[mid] == target)
return mid;
if (nums[low] <= nums[mid]) {
if (nums[low] <= target && target < nums[mid]) {
high = mid - 1;
} else
low = mid + 1;
} else {
if (nums[mid] < target && target <= nums[high])
low = mid + 1;
else
high = mid - 1;
}
}
return -1;
}First Bad Version
Let’s solve the First Bad Version problem using the Modified Binary Search pattern.
Statement
You are managing a product development team, and the latest release has failed quality checks. Because each version is built on top of the previous one, once a version is bad, every version after it is also bad.
You are given an array of n versions [1,2,…,n][1,2,…,n], and your task is to determine the first version in this sequence that is bad—the version that causes all later versions to be bad as well.
You have access to an API isBadVersion(version) that returns TRUE if a given version is bad.
Your task is to find the first bad version while minimizing the number of calls to this API.
Solution summary
The solution to this problem can be summarized as follows:
Assign two pointers to the first and the last version. Calculate the mid and check if that mid version is bad. If the mid version is bad, search for the first bad version in the first half of the range of versions. If the mid version is good, search in the second half of the range of versions. Repeat the steps to check the mid version and to divide the range of versions in two until the first and last converge.
public int firstBadVersion(int n) {
int first = 1;
int last = n;
while (first <= last) {
int mid = first + (last - first) / 2;
if (isBadVersion(mid)) {
last = mid - 1;
} else {
first = mid + 1;
}
}
return first;
}Random Pick with Weight
You’re given an array of positive integers, weights, where weights[i] is the weight of the ithith index.
Write a function, Pick Index(), which performs weighted random selection to return an index from the weights array. The larger the value of weights[i], the heavier the weight is, and the higher the chances of its index being picked.
Suppose that the array consists of the weights [12,84,35][12,84,35]. In this case, the probabilities of picking the indexes will be as follows:
Index 0: 12/(12+84+35)=9.2%12/(12+84+35)=9.2% Index 1: 84/(12+84+35)=64.1%84/(12+84+35)=64.1% Index 2: 35/(12+84+35)=26.7%35/(12+84+35)=26.7%
Lower Bound Search on Running Sum
public RandomPickWithWeight(int[] weights) {
// List to store running sums of weights
runningSums = new ArrayList<>();
// Variable to calculate running sum
int runningSum = 0;
// Iterate through the given weights
for (int w : weights) {
// Add the current weight to the running sum
runningSum += w;
// Append the running sum to the running_sums list
runningSums.add(runningSum);
}
// Store the total sum of weights
totalSum = runningSum;
}
// Method to pick an index based on the weights
public int pickIndex() {
// Generate a random number between 1 and the total sum of the array
Random random = new Random();
int target = random.nextInt(totalSum) + 1;
// Initialize low and high variables for binary search
int low = 0;
int high = runningSums.size();
// Perform binary search to find the first value higher than the target
while (low < high) {
int mid = low + (high - low) / 2;
if (target > runningSums.get(mid)) {
low = mid + 1;
} else {
high = mid;
}
}
// Return the index (low) found
return low;
}Find K Closest Elements
You are given a sorted array of integers, nums, and two integers, target and k. Your task is to return k number of integers that are close to the target value, target. The integers in the output array should be in a sorted order.
An integer, nums[i], is considered to be closer to target, as compared to nums[j] when |nums[i] - target| «_space;|nums[j] - target|. However, when |nums[i] - target| == |nums[j] - target|, the smaller of the two values is selected.
Solution summary
To summarize, we use binary search to locate the first closest element to target, then create a sliding window using two pointers to select the k closest elements. The window adjusts its size by moving the pointers based on which adjacent element is closer to the target. Eventually, the window will have the required k elements, which are then returned.
public static List<Integer> findClosestElements(int[] nums, int k, int target) {
List<Integer> closestElements = new ArrayList<>();
// If the length of 'nums' is the same as k, return 'nums'
if (nums.length == k) {
for (int num : nums) {
closestElements.add(num);
}
return closestElements;
}
// if target is less than or equal to first element in 'nums',
// return the first k elements from 'nums'
if (target <= nums[0]) {
for (int i = 0; i < k; i++) {
closestElements.add(nums[i]);
}
return closestElements;
}
// if target is greater than or equal to last element in 'nums',
// return the last k elements from 'nums'
if (target >= nums[nums.length - 1]) {
for (int i = nums.length - k; i < nums.length; i++) {
closestElements.add(nums[i]);
}
return closestElements;
}
// find the first closest element to target using binary search
int firstClosest = BinarySearch.binarySearch(nums, target);
// initialize the sliding window pointers
int windowLeft = firstClosest - 1;
int windowRight = windowLeft + 1;
// expand the sliding window until its size becomes equal to k
while ((windowRight - windowLeft - 1) < k) {
// if window's left pointer is going out of bounds, move the window rightward
if (windowLeft == -1) {
windowRight++;
continue;
}
// if window's right pointer is going out of bounds
// OR if the element pointed to by window's left pointer is closer to target than
// the element pointed to by window's right pointer, move the window leftward
if (windowRight == nums.length || Math.abs(nums[windowLeft] - target) <= Math.abs(nums[windowRight] - target)) {
windowLeft--;
}
// if the element pointed to by window's right pointer is closer to target than
// the element pointed to by window's left pointer, move the window rightward
else {
windowRight++;
}
}
// return k closest elements present inside the window
for (int i = windowLeft + 1; i < windowRight; i++) {
closestElements.add(nums[i]);
}
return closestElements;
}
Single Element in a Sorted Array
Let’s solve the Single Element in a Sorted Array problem using the Modified Binary Search pattern.
Statement
You are given a sorted array of integers, nums, where all integers appear twice except for one. Your task is to find and return the single integer that appears only once.
The solution should have a time complexity of O(logn)O(logn) or better and a space complexity of O(1)O(1).
Constraints:
1≤1≤ nums.length ≤103≤103 0≤0≤ nums[i] ≤103≤103
public static int singleNonDuplicate(int[] nums) {
// initilaize the left and right pointer
int l = 0;
int r = nums.length - 1;
while (l < r) {
// if mid is odd, decrement it to make it even
int mid = l + (r - l) / 2;
if (mid % 2 == 1) mid--;
// if the elements at mid and mid + 1 are the same, then the single element must appear after the midpoint
if (nums[mid] == nums[mid + 1]) {
l = mid + 2;
}
// otherwise, we must search for the single element before the midpoint
else {
r = mid;
}
}
return nums[l];
}The K Weakest Rows in a Matrix
You are given an m×nm×n binary matrix of 11’s (representing soldiers) and 00’s (representing civilians). The soldiers are positioned in front of the civilians, i.e., all the 11’s will appear to the left of all the 00’s in each row.
A row ii is weaker than a row jj if any of the following is TRUE:
The number of soldiers in row ii is less than the number of soldiers in row jj. Both rows have the same number of soldiers and i<ji<j.
You have to return the indexes of the kk weakest rows in the matrix ordered from weakest to strongest.
Constraints:
m=m= matrix.length n=n= matrix[i].length 2≤n,m≤1002≤n,m≤100 1≤k≤m1≤k≤m matrix[i][j] is either 00 or 11.
public static int[] findKWeakestRows(int[][] matrix, int k) {
// Get the number of rows (m) and columns (n) in the matrix
int m = matrix.length;
int n = matrix[0].length;
// Priority queue (max-heap) to store the k weakest rows
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] != a[0] ? b[0] - a[0] : b[1] - a[1]);
for (int i = 0; i < m; i++) {
// Find the strength of the row (number of soldiers)
int strength = binarySearch(matrix[i], n);
// Add the row to the heap if we haven't yet found k rows or this row is weaker than the current weakest
pq.offer(new int[]{strength, i});
// Remove the strongest row if the heap has more than k rows
if (pq.size() > k) pq.poll();
}
// Extract the k weakest rows from the heap
int[] indexes = new int[k];
// Reverse to get the order from weakest to strongest
for (int i = k - 1; i >= 0; i--) {
indexes[i] = pq.poll()[1];
}
return indexes;
}
// Helper function to perform binary search on each row to count the number of soldiers (1s)
private static int binarySearch(int[] row, int n) {
int low = 0, high = n;
while (low < high) {
int mid = low + (high - low) / 2;
// Move right if we find a soldier (1), indicating more soldiers to the right
if (row[mid] == 1) low = mid + 1;
else high = mid;
}
// low will indicate the number of soldiers in the row
return low;
}Split Array Largest Sum
Let’s solve the Split Array Largest Sum problem using the Modified Binary Search pattern.
Statement
Given an integer list nums and an integer k, split nums into k non-empty subarrays such that the largest sum among these subarrays is minimized. The task is to find the minimized largest sum by choosing the split such that the largest sum of every split of subarrays is the minimum among the sum of other splits.
Constraints:
The solution uses the binary search approach to find the optimal largest subarray sum without testing all possible splits. The binary search finds the smallest possible value of the largest subarray sum and applies searching over the range of possible values for this largest sum. But how do we guess this value? We guess the value using a certain range. Here’s how:
Left boundary: The maximum element in the array is the minimum possible value for the largest subarray sum. This is because any valid subarray must have a sum at least as large as the largest element. Right boundary: The maximum possible value for the largest subarray sum is the sum of all elements in the array. You would get this sum if the entire array were one single subarray.
The binary search iteratively tests midpoints in the above ranges. It determines whether dividing the array results in at most k subarrays will result in the smallest largest sum. If it does, the search shifts to lower values to minimize the largest sum. Otherwise, it shifts to higher values. Still, there might be subarrays whose sum could be smaller, so the search keeps going until the search range crosses each other, i.e., left boundary > right boundary.
// Check if the array can be split into k or fewer subarrays with the maximum sum as mid
public boolean canSplit(int[] nums, int k, int mid) {
// Initialize the count of subarrays and the current sum of the current subarray
int subarrays = 1;
int currentSum = 0;
for (int num : nums) {
// Check if adding the current number exceeds the allowed sum (mid)
if (currentSum + num > mid) {
// Increment the count of subarrays
subarrays += 1;
// Start a new subarray with the current number
currentSum = num;
// If the number of subarrays exceeds the allowed k, return False
if (subarrays > k) {
return false;
}
} else {
// Otherwise, add the number to the current subarray
currentSum += num;
}
}
// Return True if the array can be split within the allowed subarray count
return true;
}
public int splitArray(int[] nums, int k) {
// Set the initial search range for the largest sum:
// Minimum is the largest number in the array, and maximum is the sum of all numbers
int left = Integer.MIN_VALUE, right = 0;
for (int num : nums) {
left = Math.max(left, num);
right += num;
}
// Perform binary search to find the minimum largest sum
while (left < right) {
// Find the middle value of the current range
int mid = (left + right) / 2;
// Check if the array can be split into k or fewer subarrays with this maximum sum
if (canSplit(nums, k, mid)) {
// If possible, try a smaller maximum sum
right = mid;
} else {
// Otherwise, increase the range to allow larger sums
left = mid + 1;
}
}
// Return the smallest maximum sum that satisfies the condition
return left;
}Find Minimum in Rotated Sorted Array II
Let’s solve the Find Minimum in Rotated Sorted Array II using the Modified Binary Search pattern.
Statement
Imagine you have an array, nums, of length nn that was originally sorted in non-decreasing (ascending) order. This array has been rotated between 11 and nn times. For example, the sorted array [0,2,3,3,5,7,11][0,2,3,3,5,7,11] can become:
[5,7,11,0,2,3,3][5,7,11,0,2,3,3], if rotated 33 times [0,2,3,3,5,7,11][0,2,3,3,5,7,11], if rotated 77 times
A single rotation moves the last element to the front. So, if the original array is [a[0],a[1],…,a[n−1]][a[0],a[1],…,a[n−1]], rotating it once produces [a[n−1],a[0],a[1],…,a[n−2]][a[n−1],a[0],a[1],…,a[n−2]].
You are given a sorted, rotated array, nums, that may include duplicate elements. Your job is to return the minimum element in the array.
The solution uses the binary search approach to find the optimal largest subarray sum without testing all possible splits. The binary search finds the smallest possible value of the largest subarray sum and applies searching over the range of possible values for this largest sum. But how do we guess this value? We guess the value using a certain range. Here’s how:
Left boundary: The maximum element in the array is the minimum possible value for the largest subarray sum. This is because any valid subarray must have a sum at least as large as the largest element. Right boundary: The maximum possible value for the largest subarray sum is the sum of all elements in the array. You would get this sum if the entire array were one single subarray.
The binary search iteratively tests midpoints in the above ranges. It determines whether dividing the array results in at most k subarrays will result in the smallest largest sum. If it does, the search shifts to lower values to minimize the largest sum. Otherwise, it shifts to higher values. Still, there might be subarrays whose sum could be smaller, so the search keeps going until the search range crosses each other, i.e., left boundary > right boundary.
public int findMin(int[] nums) {
// Set two pointers at the beginning and end of the array
int low = 0, high = nums.length - 1;
// Iterate through the array as long as low is less than high
while (low < high) {
// Compute the middle index of the current range
int pivot = (low + high) / 2;
// If the element at pivot is less than the element at high,
// shrink the search space by setting high = pivot
if (nums[pivot] < nums[high])
high = pivot;
// If the element at pivot is greater than the element at high,
// update the low pointer to pivot + 1
else if (nums[pivot] > nums[high])
low = pivot + 1;
// If both values are equal, safely reduce the search space by shrinking high by one
else
high--;
}
// When the loop terminates, low points to the minimum element
return nums[low];
}Maximum Running Time of N Computers
Let’s solve the Maximum Running Time of N Computers problem using the Modified Binary Search Pattern.
Statement
You are given an integer, n, representing the number of computers, and a 0-indexed integer array, batteries, where batteries[i] denotes the number of minutes the ithith battery can power a computer.
Your goal is to run all n computers simultaneously for the maximum possible number of minutes using the available batteries.
Initially, you may assign at most one battery to each computer. After that, at any moment, you may remove a battery from a computer and replace it with another battery—either an unused battery or one taken from another computer. This replacement process can be repeated any number of times and takes no time.
Each battery can power any computer multiple times, but only until it is completely drained. Batteries cannot be recharged.
Return the maximum number of minutes you can run all n computers simultaneously.
public static int maxRunTime(int[] batteries, int n) {
// Calculate the total available battery power
long totalPower = 0;
for (int b : batteries) {
totalPower += b;
}
// The search range for the maximum possible runtime is [0, totalPower / n]
long left = 0;
long right = totalPower / n;
// Perform binary search to find the maximum possible runtime
while (left < right) {
// Calculate the midpoint, biased toward the right to avoid infinite loop
long mid = right - (right - left) / 2;
// Calculate how much total power can be used if we try to run for 'mid' minutes
// Each battery can contribute up to 'mid' minutes (not more), so we cap it
long usable = 0;
for (int b : batteries) {
usable += Math.min(b, mid);
}
// Check if we have enough usable power to run 'n' computers for 'mid' minutes
if (usable >= mid * n) {
// Feasible: Try to see if we can run for even more time
left = mid;
} else {
// Not feasible: We need to try a shorter runtime
right = mid - 1;
}
}
return (int) left;
}Minimize Max Distance to Gas Station
Let’s solve the Minimize Max Distance to Gas Station problem using the Modified Binary Search pattern.
Statement
You are given an integer array, stations, representing the positions of existing gas stations along the x-axis. You are also given an integer k, indicating the number of additional gas stations you must add. These new gas stations can be placed at any position along the x-axis, including non-integer locations.
A penalty is the maximum distance between two adjacent gas stations after placing the k new stations. Your task is to return the smallest possible value of this penalty. An answer is correct if it is within 10−610−6 of the actual answer.
Constraints:
10≤10≤ stations.length ≤2000≤2000 0≤0≤ stations[i] ≤108≤108 The stations array is sorted in a strictly increasing order. 1≤1≤ k ≤106≤10
public class Solution {
public double minimizeGasDistance(int[] stations, int k) {
double left = 0.0;
double right = stations[stations.length - 1] - stations[0];
final double epsilon = 1e-6;
while (right - left > epsilon) {
double mid = (left + right) / 2;
if (isPossible(stations, k, mid)) {
right = mid; // Try smaller penalty
} else {
left = mid; // Need larger penalty
}
}
return left;
}
private boolean isPossible(int[] stations, int k, double distance) {
int requiredStations = 0;
for (int i = 1; i < stations.length; i++) {
double gap = stations[i] - stations[i - 1];
// Key fix: stations needed = ceil(gap/distance) - 1
int needed = (int) Math.ceil(gap / distance) - 1;
requiredStations += Math.max(0, needed);
if (requiredStations > k) {
return false;
}
}
return true;
}
}
double left = MIN, right = MAX;
while (right - left > 1e-6) {
double mid = (left + right) / 2;
if (canHandle(mid)) left = mid; // Push left up
else right = mid;
}
return left;
Divide Chocolate
Let’s solve the Divide Chocolate problem using the Modified Binary Search pattern.
Statement
You have a chocolate bar made up of several chunks, and each chunk has a certain sweetness, given in an array called sweetness. You want to share the chocolate with k friends. To do this, you’ll make k cuts to divide the bar into k + 1 parts. Each part will consist of consecutive chunks.
Being a kind person, you’ll take the piece with the minimum total sweetness and give the other pieces to your friends.
Your task is to find the maximum total sweetness of the piece you will receive if you cut the chocolate bar optimally.
Constraints:
0≤0≤ k << sweetness.length ≤103≤103 1≤1≤ sweetness[i] ≤103≤10
public class Solution {
// Helper function to check if it's possible to divide chocolate into at least k + 1 pieces
// such that each piece has at least `minSweetness` total sweetness
public boolean canDivide(int[] sweetness, int k, int minSweetness) {
int totalSweetness = 0;
int pieces = 0;
for (int sweet : sweetness) {
totalSweetness += sweet; // Keep adding sweetness values
if (totalSweetness >= minSweetness) {
pieces++; // We found one valid piece
totalSweetness = 0; // Start collecting for the next piece
}
}
return pieces >= k + 1; // Check if we have enough pieces
}
// Main function to find the maximum minimum sweetness we can get after dividing
// the chocolate into k + 1 pieces
public int maximizeSweetness(int[] sweetness, int k) {
// The minimum possible sweetness is 1, and the maximum is total // (k + 1)
int low = 1;
int high = Arrays.stream(sweetness).sum() / (k + 1);
int result = low; // Initialize result
// Apply binary search on the sweetness value
while (low <= high) {
int mid = (low + high) / 2; // Guess a possible minimum sweetness
if (canDivide(sweetness, k, mid)) {
result = mid; // This sweetness is possible, try for a higher one
low = mid + 1; // Move to the right half
} else {
high = mid - 1; // Not possible, move to the left half
}
}
return result; // Return the best found result
}Number of Flowers in Full Bloom
You are given a 0-indexed 2D integer array, flowers, where each element flowers[i] =[starti,endi]=[starti,endi] represents the time interval during which the ithith flower is in full bloom (inclusive).
You are also given a 0-indexed integer array, people, of size nn, where people[i] denotes the time at which the ithith person arrives to view the flowers.
For each person, determine how many flowers are in full bloom at their arrival time. Return an integer array, ans, of length nn, where ans[i] is the number of blooming flowers when the ithith person arrives.
Constraints:
1 ≤≤ flowers.length ≤≤ 103103 flowers[i].length ==2==2 1 ≤≤ startistarti ≤≤ endiendi ≤≤ 104104 1 ≤≤ people.length ≤≤ 103103 1 ≤≤ people[i] ≤≤ 104104
public class Solution
{
public static int[] fullBloomFlowers(int[][] flowers, int[] people)
{
List<Integer> starts = new ArrayList<>();
List<Integer> ends = new ArrayList<>();
// Separate start and end times
for (int[] f : flowers) {
starts.add(f[0]);
ends.add(f[1] + 1); // inclusive handling
}
Collections.sort(starts);
Collections.sort(ends);
int[] ans = new int[people.length];
for (int i = 0; i < people.length; i++) {
int person = people[i];
// Number of flowers started <= person
int started = binarySearch(starts, person);
// Number of flowers ended < person
int ended = binarySearch(ends, person);
ans[i] = started - ended;
}
return ans;
}
// Binary search
private static int binarySearch(List<Integer> arr, int target) {
int left = 0, right = arr.size();
while (left < right) {
int mid = (left + right) / 2;
if (target < arr.get(mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left; // number of elements <= target
}
Koko Eating Bananas
Let’s solve the Koko Eating Bananas problem using the Modified Binary Search pattern.
Statement
Koko has nn piles of bananas in front of her, where the ithith pile has piles[i] bananas. The guards have left and will return in h hours, and Koko must finish all the bananas before they come back.
Before eating, Koko chooses an integer as an eating speed kk (bananas per hour). She keeps this speed constant throughout.
In each hour, Koko selects one pile of bananas and eats from it according to the following rules:
If the pile contains at least kk bananas, she eats exactly kk bananas from it. If the pile contains fewer than kk bananas, she eats all the bananas from that pile and does not eat from any other pile during that hour.
Your task is to return the minimum eating speed kk that allows Koko to finish all the bananas within h hours before the guards return.
public int minEatingSpeed(int[] piles, int h) {
// Find the largest pile to set the right boundary
int maxPile = 0;
for (int pile : piles) {
if (pile > maxPile) maxPile = pile;
}
// Set the initial search boundaries:
int left = 1, right = maxPile;
// Binary search until the range collapses to one number.
while (left < right) {
int mid = (left + right) / 2;
long hours = 0;
// Calculate how many hours it takes to eat all piles at this speed
for (int pile : piles) {
// Ceiling division to count full hours needed per pile
hours += (pile + mid - 1) / mid;
}
if (hours <= h) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}**Search Insert Position
**
Let’s solve the Search Insert Position problem using the Modified Binary Search pattern.
Statement
Given a sorted array of distinct integers, nums, and an integer, target, return the index of target if it exists in the array.
If the target is not present, return the index where it should be inserted to maintain the sorted order.
Your algorithm must run in the O(logn)O(logn) time.
public static int searchInsert(int[] nums, int target) {
// Initialize the search boundaries
int left = 0, right = nums.length - 1;
// Perform binary search
while (left <= right) {
int mid = (left + right) / 2; // Middle index
// If target is found at mid, return its index
if (nums[mid] == target) {
return mid;
}
// If target is bigger, ignore left half
else if (nums[mid] < target) {
left = mid + 1;
}
// If target is smaller, ignore right half
else {
right = mid - 1;
}
}
// If target not found, 'left' indicates the correct insertion index
return left;
}Find Peak Element
Let’s solve the Find Peak Element problem using the Modified Binary Search pattern.
Statement
You’re given a 0-indexed integer array nums. An index i is called a peak if nums[i] is strictly greater than its neighboring values (the elements immediately to its left and right, if they exist). Assume the array has virtual boundaries where nums[-1] = nums[n] = -∞, so the first and last elements can also be peaks.
Your task is to return the index of any one peak element (if there are multiple peaks, any valid peak index is acceptable), and your solution must run in O(logn)O(logn) time.
public static int findPeak(int[] nums) {
int l = 0, r = nums.length - 1;
// Binary search for a peak
while (l < r) {
int mid = (l + r) / 2;
// If the middle element is less than the next one,
// we are in an ascending slope → a peak exists on the right side.
if (nums[mid] < nums[mid + 1]) {
// Move to the right half (peak is guaranteed there)
l = mid + 1;
} else {
// We are on a descending slope or at a peak.
// A peak exists on the left side (including mid).
r = mid;
}
}
// When l == r, this index must be a peak.
return l;
}Search in Rotated Sorted Array II
Try to solve the Search in Rotated Sorted Array II problem.
Statement
You are required to find an integer value target in an array arr of non-distinct integers. Before being passed as input to your search function, arr has been processed as follows:
It has been sorted in non-descending order. It has been rotated around some pivot kk, such that, after rotation, it looks like this: [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]. For example, [10, 30, 40, 42, 42, 47, 78, 90, 901], rotated around pivot k=5k=5 becomes [47, 78, 90, 901, 10, 30, 40, 42, 42].
Return TRUE if t exists in the rotated, sorted array arr, and FALSE otherwise, while minimizing the number of operations in the search.
public class Solution {
public static boolean search(int[] arr, int target) {
// Replace this placeholder return statement with your code
int l =0; int r= arr.length-1;
while(l<=r){
int m = l + (r-l)/2;
if(arr[m] == target) return true;
if(arr[l]<arr[m] ){
if (target < arr[m] && target >= arr[l]) r= m-1;
else l =m+1;
}
if(arr[m]<arr[r] ){
if (target <= arr[r] && target > arr[m]) l= m+1;
else r =m-1;
}
if(arr[m] == arr[l]) l++;
if(arr[m] == arr[r]) r--;
}
return false;
}
}
