Problems based on the Binary Search (Big List) (Goals Tracking)
- Steps used in Binary Search
- Binary Search in Java
- Order-Agnostic Binary Search
- When do we apply Binary Search ?
- Templates(Patterns) in Binary Search
- Problems on Binary Search
- Easy
- Square Root
- Guess Number Higher or Lower
- First Bad Version
- Two Sum II - Input array is sorted
- Valid Perfect Square
- Arranging Coins(Easy)
- Find Smallest Letter Greater Than Target
- Kth Missing Positive Number
- Search Insert Position
- Peak Index in a Mountain Array
- Count Negative Numbers in a Sorted Matrix
- Intersection of Two Arrays
- Intersection of Two Arrays II
- Fair Candy Swap
- Check If N and Its Double Exist
- Special Array With X Elements Greater Than or Equal X
- Binary Search
- Medium
- Find First and Last Position of Element in Sorted Array
- Single Element in a Sorted Array
- Search in Rotated Sorted Array
- Search in Rotated Sorted Array II
- Find Minimum in Rotated Sorted Array
- Find Peak Element
- Find Right Interval
- Reach a Number
- Maximum Value at a Given Index in a Bounded Array
- Koko Eating Bananas
- Minimum Absolute Sum Difference
- Search a 2D Matrix
- Find a Peak Element II
- Frequency of the Most Frequent Element
- Find the Duplicate Number
- Capacity To Ship Packages Within D Days
- 4 Sum
- Hard
- Easy
Binary Search Problems (SDE Sheet - Day 11) (Striver) (Goals Tracking)
- Difficulity: Medium to Hard
Condition: Array must be sorted
- Find the middle element (Type 1)
- ( mid = ( start + end ) / 2 )
- Optimization for finding middle element (Type 2)
- mid = start + ( (end - start) / 2 )
- Problem before: Integer Overflow!!! - might be possible that (start + end) exceeds the range of int in Java
- If target > mid => search in the right
- Else => search in left
- If middle element == target element => return (answer)
package com.aswin;
public class BinarySearch {
public static void main(String[] args) {
int[] arr = {-18, -12, -4, 0, 2, 3, 4, 15, 16, 18, 22, 45, 89};
int target = 3;
int ans = binarySearch(arr, target);
System.out.println(ans);
}
// return the index
// return -1 if it does not exist
static int binarySearch(int[] arr, int target) {
int start = 0;
int end = arr.length - 1;
while(start <= end) {
// find the middle element
// int mid = (start + end) / 2;
// Problem: might be possible that (start + end) exceeds the range of int in Java
int mid = start + ( (end - start) / 2 );
if(target < arr[mid]) {
end = mid - 1;
} else if (target > arr[mid]) {
start = mid + 1;
} else {
// ans found
return mid;
}
}
return -1;
}
}
- During Binary Search, when we access the array elements (at both ends) in search space, we must avoid Array Index Out Of Bounds Error.
- So, always use the following function
int safeGet(int[] A, int i) {
if(0 <= i && i < A.length) {
return A[i];
} else {
return Integer.MAX_VALUE;
}
}
- When the array order is unknown ( ascending order or descending order ?)
- Find the middle element
- ( mid = ( start + end ) / 2 )
- If target > mid => search in the left
- If target < mid => search in right
- Else middle element == target element (answer)
- Just check the start and end
- Steps :
- if start < end => Ascending order
- else => Descending order
- One small change in Binary Search logic: find whether the array is sorted in ascending or descending
boolean isAsc = arr[start] < arr[end]
package com.aswin;
public class OrderAgnosticBS {
public static void main(String[] args) {
int[] arr = {-18, -12, -4, 0, 2, 3, 4, 15, 16, 18, 22, 45, 89};
int target = 3;
int ans = orderAgnosticBS(arr, target);
System.out.println(ans);
}
// return the index
// return -1 if it does not exist
static int orderAgnosticBS(int[] arr, int target) {
int start = 0;
int end = arr.length - 1;
// find whether the array is sorted in ascending or descending
boolean isAsc = arr[start] < arr[end];
while(start <= end) {
// find the middle element
// int mid = (start + end) / 2;
// Problem: might be possible that (start + end) exceeds the range of int in Java
int mid = start + ( (end - start) / 2 );
if(arr[mid] == target) {
// ans found
return mid;
}
if(isAsc) {
if(target < arr[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
else {
if(target > arr[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
}
return -1;
}
}
- Sorted array (If we are given as input)
- When you are required to get one particular answer and you are following a continuous sequence to get the answer:
- Square Root of a number
- Maximize the minimum answer
- Minimize the maximum answer
- Maximize the answer
- Minimize the answer
- much more ...
- Difficulity: Easy to Hard
- Ceiling of number: Smallest element in array which is greater than or equal to target
- Steps
-
- Find the closest or equal number to target
-
- Find all the numbers which are greater than the previous result (Binary Search)
-
- Return the smallest number from the previous category
- Consider the following example:
- arr = [2, 3, 5, 9, 14, 16, 18], target = 14
- ceiling(arr, target=14) = 14
- ceiling(arr, target=15) = 16
- ceiling(arr, target=4) = 5
- ceiling(arr, target=9) = 9
- If target is found, return the target
- Else return the start
- Because when the condition is violated in the while loop:
start = end + 1
-
start target end => end target start
- So the answer is not in this range, and the smallest element which is greater than or equal to target is the start
Java Code Link: Ceiling of a number
- Ceiling of number: Greatest element in array which is smaller than or equal to target
- Steps
-
- Find the closest or equal number to target
-
- Find all the numbers which are smaller than the previous result (Binary Search)
-
- Return the greatest number from the previous category
- Consider the following example:
- arr = [2, 3, 5, 9, 14, 16, 18], target = 14
- floor(arr, target=4) = 3
- floor(arr, target=9) = 9
- floor(arr, target=14) = 14
- floor(arr, target=19) = 18
- If target is found, return the target
- Else return the end
- Because when the condition is violated in the while loop:
start = end + 1
-
start target end => target end start
- So the answer is not in this range, and the greatest element which is smaller than or equal to target is the end
Java Code Link: Floor of a number - JavaCode
- Similar to Ceiling of a number
- Change: Ignore mid == target condition
- Change: Return start % arr.length as the result
LeetCode Link: Find Smallest Letter Greater Than Target - LeetCode
Java Code Link: Find Smallest Letter Greater Than Target - JavaCode
- Apply Binary Search Twice:
- Find the first occurrence of the target - Change: Update ans and end each time
- Find the last occurrence of the target - Change: Update ans and start each time
- In an infinte array of numbers, the size is unknown.
- Binary search divides the array by two for each iteration following Top - down approach
- For this problem, as we are unaware about the end pointer, we will follow Bottom - up approach
- Bottom-up : Start with a small chunk of array and double up the size of the chunk by two for every iteration
- Apply Binary search for each chunk and keep doubling the chunk until the element is found.
-
Mountain Array is also known as Bitonic array.
-
In this array, the numbers in first part are sorted in increasing order and the second part in decreasing order.
-
Peak element is nothing but the maximum element in the array.
-
So, we have two cases where we can compare adjacent elements:
- Ascending part where we can update the start = mid + 1
- Descending part where we can update the end = mid
-
In the end, start == end and pointing to the largest number because of the 2 checks above
-
start and end are always trying to find the max element in the above 2 checks
-
Hence, when they are pointing to just one element, that is the max one because that is what the checks say
-
More elaboration: at every point of the time for start and end,
-
they have the best possible answer till that time and if we are saying that only one item is remaining
-
hence because of above line that is the best possible ans
- Similar to Peak Index in Mountain Array, except the target is given
- Here, we can first find the Peak Index
- Then, apply Order Agnostic Binary Search in both parts of the Mountain array:
0 -> peakIndex
peakIndex+1 -> arr.length - 1
- And, finally return the answer
- Consider an array =
[2, 4, 5, 7, 8, 9, 10, 12]
- After 1st rotation, array =
[12, 2, 4, 5, 7, 8, 9, 10]
- After 2nd rotation, array =
[10, 12, 2, 4, 5, 7, 8, 9]
- pivot is from where your next numbers are ascending
- pivot is also the largest number
- For example:
[3, 4, 5, 6, 7, 0, 1, 2]
- Here, the is pivot = 7
- Both parts before & after the pivot is sorted in ascending order
- So, we can follow the following steps:
- Find pivot
- Search target in first half => Simple BS
(0 -> pivot)
- If still not found, search target in second half => Simple BS
(pivot+1, end)
- Now, the problem is to find the pivot:
- Consider
[3, 4, 5, 6, 7, 0, 1, 2]
- We can observe that only two elements
7, 0
are descending - So, when do we find the answer:
- Case 1: When mid > mid+1 element, then mid is the pivot
- Case 2: When mid < mid-1 element, then mid-1 is the pivot
- Case 3: When start >= mid element, then end = mid - 1
- Case 4: When start < mid element, then start = mid + 1
- ( Explanation for case 3 & 4: if mid was pivot it would've returned by case 1 & 2... )
- ( Hence, proved that bigger number lies behind in case 3 and ahead in case 4, so ignore mid in case 3 and 4 using mid (+ or -) 1 )
- Consider
- Now, we have to find the target:
- If target == arr[pivot] return pivot
- If target >= arr[0], Search target in first half => Simple BS
(0 -> pivot)
- If target < arr[pivot] search target in second half => Simple BS
(pivot+1, end)
-
The approach for duplicates are same as the previous problem except
- The while loop should terminate when start>=end
- The Case 3 & 4 will not work for duplicates
-
So, we can skip the duplicates by comparing start, mid and end only if they are not pivot elements
-
And then we can start reducing the search space based on the comparision of start, mid, and end
- Similar to previous approaches except
- We return 0 if array's pivot is -1
- Else we return the pivot+1 as the answer
- Because the array rotates pivot times, and as we get 0-indexed pivot, we return pivot+1 as the answer.
- Find the minimum (minAns) and maximum no. of splits (maxAns) we can make
- Take the minAns and maxAns as start and end respectively
- Apply binary search such that
- the mid will be (minAns + maxAns) / 2
- Traverse the array and calculate the cummulative sum to calculate how many pieces you can divide the array with this mid (max sum)
- if sum becomes greater than mid, then reset sum to current number, and increment the no. of pieces
- else continue adding sum
- Now, apply checks for binary search
- If no. of pieces are greater than
m
(given no. of partitions) then update start = end + 1 - Else update end = mid
- If no. of pieces are greater than