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