Modified Binary Search
A modified version of binary search that applies to rotated arrays, unsorted arrays, or specialized conditions. ex. finding the minimum element in a rotated sorted array. These type of problems cannot be solved with a standard binary search, as the array may not be fully sorted. Instead, we can use a modified binary search approach that takes into account of the unconventional structure of the array. TC is same as binary search, O(log n)
Binary search works beautifully on sorted arrays—but real problems often bend that rule. Rotated arrays are a classic example where the order is partially preserved, and we can still exploit that structure.
Modified binary search is about asking a slightly different question at every step: which part of the array is still sorted, and where could the answer lie?
Example : Find the minimum element in a rotated sorted array.
arr = [4,5,6,7,0,1,2] // minimum element 0 at index 5
Key observations:
- The index of the minimum element equals the number of rotations.
- The minimum element is the only element smaller than its neighbors.
- At least one half of the array is always sorted.
Instead of checking both halves, we eliminate one half using the sorted property.
Algorithm:
- Find the middle element.
- Compare it with the rightmost element.
- Decide which half contains the minimum.
class Solution {
public int findMin(int[] nums) {
int left = 0, right = nums.length-1;
while(left < right){
int mid = left + (right - left) / 2;
if(nums[mid] > nums[right]){
left = mid + 1;
}else{
right = mid;
}
}
return nums[left];
}
}
Example : Search in Rotated Sorted Array (LC 33)[https://leetcode.com/problems/search-in-rotated-sorted-array]
Here, instead of finding the minimum, we locate a target.
At every step:
- One side (left or right) is guaranteed to be sorted.
- We check if the target lies within that sorted range.
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (target == nums[mid])
return mid;
// if left side is sorted use this
if (nums[left] < nums[mid]) {
// check if target is in the range (both ends), if not update "left"
if (target > nums[mid] || target < nums[left]) {
left = mid + 1;
} else {
right = mid - 1;
}
} else { // if right side is sorted use this (obviously)
if (target < nums[mid] || target > nums[right]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
}
return -1;
}
}
Example : Search in Rotated Sorted Array II (LC 81)[https://leetcode.com/problems/search-in-rotated-sorted-array-ii]
Duplicates introduce ambiguity—sometimes we can't tell which side is sorted.
In that case, we shrink the search space linearly.
class Solution {
public boolean search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (target == nums[mid])
return true;
// if left side is sorted use this
if (nums[left] < nums[mid]) {
// check if target is in the range (both ends), if not update "left"
if (target > nums[mid] || target < nums[left]) {
left = mid + 1;
} else {
right = mid - 1;
}
} else if (nums[left] > nums[mid]) { // if right side is sorted use this (obviously)
if (target < nums[mid] || target > nums[right]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
// if there are duplicate values and if left == mid it is obvious that left will be furthur and less than mid,
// we will check with every pass now. if all values are same and the target is not found eventually, left > right
// and return false.
else {
left++;
}
}
return false;
}
}