Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).

You are given a target value to search. If found in the array return true, otherwise return false.

Example 1:

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

Example 2:

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false

Before solving this problem, please look at the similar problem. Search in Rotated Sorted Array.

Given an array sorted in ascending order and is rotated at some pivot, given a target value to search, if found in the array return its index

The only difference between the above solution and this one is, we check for the duplicates, if there are any we skip them.

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++

/*
* File     : search_in_sorted_array_II.cpp
* Purpose  : Search the target element in a sored array, but reversed at an index
*/
#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