Example 1: Input: nums = [2,5,6,0,0,1,2], key = 0 Output: true
Before solving this problem, please look at the similar problem. Search in Rotated Sorted Array.
We achieve this by below 2 lines:
while (low < high && array[low] == array[low + 1]) low++; // skip duplicates from the left while (high > low && array[high] == array[high - 1]) high--; // skip duplicates from the right
Solution in C++
#include<iostream>
#include<vector>
using namespace std;
int binary_search_modified(vector<int>& array, int target)
{
int low = 0;
int high = array.size()-1;
while (low <= high)
{
while (low < high && array[low] == array[low + 1]) low++; // skip duplicates from the left
while (high > low && array[high] == array[high - 1]) high--; // skip duplicates from the right
int mid = ( high-low )/2 + low;
if (array[mid] == target)
return mid;
if (array[mid] < array[high])
{
if ( array[mid] < target && target <= array[high])
low = mid + 1;
else
high = mid - 1;
}
else
{
if(array[low] <= target && target < array[mid])
high = mid - 1;
else
low = mid + 1;
}
}
return -1;
}
int main()
{
vector<int> array;
array.push_back(2);
array.push_back(5);
array.push_back(6);
array.push_back(0);
array.push_back(0);
array.push_back(1);
array.push_back(2);
int target = 0;
for (int i = 0; i < array.size(); i++)
{
cout <<array[i] << " ";
}
cout<<endl;
int index = binary_search_modified (array, target);
if (index)
{
cout<<"The target = "<<target <<" found at index = "<< index<<endl;
}
else
{
cout<<"Target not found"<<endl;
}
}Output:
2 5 6 0 0 1 2 The target = 0 found at index = 3
