Binary Search is an efficient algorithm for finding a target element in a sorted array. It works by repeatedly dividing the search interval in half
- If the target value is less than the middle element, the search continues on the left half.
- If the target value is greater than the middle element, the search continues on the right half.
- If the middle element is the target, the search is complete.
Key Condition: The array must be sorted.
Binary Search Algorithm
Pseudo-Code:
cpp
1. Initialize two pointers, `left = 0` and `right = n-1`
2. While `left <= right`:
a. Calculate `mid = left + (right - left) / 2`
b. If `target == arr[mid]`, return the index `mid`
c. If `target < arr[mid]`, search in the left half: `right = mid - 1`
d. If `target > arr[mid]`, search in the right half: `left = mid + 1`
3. If the element is not found, return -1.Recursive vs Iterative Approach
Iterative Binary Search
cpp
int binarySearchIterative(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
// int mid = left + (right - left) / 2;
int mid=(i+((j-i)>>1)) ;
if (nums[mid] == target) return mid; // Target found
else if (nums[mid] > target) right = mid - 1; // Search left half
else left = mid + 1; // Search right half
}
return -1; // Target not found
}Recursive Binary Search
cpp
int binarySearchRecursive(vector<int>& nums, int left, int right, int target) {
if (left > right) return -1; // Base case: Target not found
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid; // Target found
else if (nums[mid] > target) return binarySearchRecursive(nums, left, mid - 1, target); // Search left half
else return binarySearchRecursive(nums, mid + 1, right, target); // Search right half
}Time Complexity
- Time Complexity: (O(log n))
- Space Complexity:
- Iterative: (O(1)) (constant space).
- Recursive: (O(log n)) due to recursive function calls.
Lower bound & upper bound
lower_bound - returns iterator to first element in the given range which is Equal_to or Greater than val.
upper_bound - returns iterator to first element in the given range which is Greater than val.
Common Problems
Finding the First or Last Occurrence of a Target
- Problem: Find First and Last Position of Element in Sorted Array
- Hint:Use binary search with slight modifications to find the first or last index where the target occurs. OR
cpp
int lower_index = lower_bound(nums.begin(), nums.end(), target) - nums.begin() ;
if (lower_index == nums.size() || nums[lower_index] != target) {
return {-1, -1};
}
int upper_index = upper_bound(nums.begin(), nums.end(), target) - nums.begin() - 1 ;
return {lower_index,upper_index};Find Minimum in Rotated Sorted Arra
- Problem: Find Minimum in Rotated Sorted Array
cpp
class Solution {
public:
int findMin(vector<int>& nums) {
int n=nums.size() ;
int left=0,right=n-1 ;
while(left<right)
{
int mid=left+(right-left)/2 ;
if(nums[mid]>nums[right])
{
left=mid+1 ;
}
else right=mid ;
}
return nums[left] ;
}
};Search in a Circularly Sorted Array
- Problem: Search in Rotated Sorted Array
- Hint:
- Use binary search to identify the pivot point where the array is rotated.
- Perform binary search on the appropriate half (either left or right of the pivot) where the target could be.
Find Row with Maximum Ones in a Matrix Sorted by Rows
- Problem: Row with Maximum Number of 1s
- Hint:
- Start from the top-right corner of the matrix.
- If you encounter a 1, move left; if you encounter a 0, move down.
- Keep track of the row with the maximum number of 1s.
Find the square root of a given number n using binary search with a specified precision
Find the square root of a given number n using binary search with a specified precision .
- Approach:
- Use binary search to find the integer part of the square root.
- Refine the result to include the fractional part up to the desired precision p.
cpp
double morePrecision(int n, int precision, int tempSol) {
double factor = 1; // Factor for each decimal place
double ans = tempSol; // Start with the integer part solution
// Loop to add more precision
for (int i = 0; i < precision; i++) {
factor /= 10; // Reduce the factor by 10 (moving to the next decimal place)
// Linear search for each decimal place
for (double j = ans; j * j <= n; j += factor) {
ans = j; // Update ans if j * j is still <= n
}
}
return ans;
}Find an Element in a Matrix Sorted by Rows
- Problem: Search a 2D Matrix
- Hint:
- Treat the matrix as a 1D sorted array by flattening it conceptually.
- Use binary search to search for the target element in the matrix.
Egg Dropping Puzzle
- Problem: Super Egg Drop
- Hint:
- This is a dynamic programming problem.
- Start with one egg and incrementally add eggs, exploring the minimum number of attempts needed.
- Think of the problem in terms of worst-case scenario at each floor drop.
Kth Smallest Element in a Sorted Matrix
- Problem: Kth Smallest Element in a Sorted Matrix
- Hint:
- The matrix is row-wise and column-wise sorted.
- Use a min-heap (priority queue) to push elements from the matrix in order, or binary search on the value range.
Distribute n Candies Among k People
- Problem: Distribute Candies to People
- Hint:
- Distribute the candies in rounds, where each person receives an incrementally increasing number of candies.
- Keep track of how many candies remain and adjust accordingly at each step.
- Use modulo operations to loop through the people.
Allocate Minimum Number Of Pages
- Problem: Split Array Largest Sum
cpp
class Solution {
public:
bool possible(vector<int>&nums ,int k,int n,int mid)
{
int cnt=1 ;
int sum=0 ;
for(int i=0;i<n;i++)
{
sum+=nums[i] ;
if(sum>mid)
{
cnt++ ;
sum=nums[i] ;
}
if(cnt>k) return 0 ;
}
return 1 ;
}
int splitArray(vector<int>& nums, int k) {
int n=nums.size() ,ans=0;
if(n<k) return -1 ;
int total_sum=accumulate(nums.begin(),nums.end(),0) ;
int mx=*max_element(nums.begin(),nums.end()) ;
int left=mx, right=total_sum ;
while(left<=right)
{
int mid=left+((right-left)>>1) ;
if(possible(nums,k,n,mid))
{
ans=mid ;
right=mid-1;
}
else left=mid+1 ;
}
return ans ;
}
};