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

Initial Sorted array:

[0,1,2,4,5,6,7]

After rotation it becomes [4,5,6,7,0,1,2].

Target = 0

Index = 4 [as array index starts from 0]

This problem can be solved by 2 ways:

1. Linear Search

2. Modified Binary search

In this solution we search the element one by one, and return the index. But come on, we shall give the interviewer the 2nd solution.

We can solve this by using modified binary search.

In Binary search, we divide the sorted array in to 2 parts. And change the lower index and higher index.

The same solution cannot be applied here, because the array is not sorted. But we know that, in a divided array there is always a half that is sorted. Hence we need to find whether the number is in the sorted part or in the rotated part.

We use the below code to achieve the same:

int binary_search_modified(vector<int>& array, int target) 
{
    int low = 0;
    int high = array.size()-1;

    while (low <= high) 
    {
        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;
}

Input: 
4, 5, 6, 7, 0, 1, 2

Target = 0

Pass 1:
    low = 0
    high = 6

    while(0 <= 6) true
        mid = (6-0) / 2 + 0
            = 3
        if array[3] == target ? false

        if(array[3] < array[6]) => (7 < 2) ? false
            else case
                if(array[0] <= target && target < array[3]) => (4 <= 0 && 0< 7) false
                    else case
                        low = mid + 1 => 3 + 1 >4

Pass 2:
    low = 4
    high = 6
    while (4 <= 6) true
        mid = (6 - 4)/2 + 4 = 5
    if(array[5] == target) ? false
    if(array[5] < array [6]) => (1 < 2 ) true
        if(array[5] < target) && (target <= array[6]) => (1<0 && 0<=2) false
            high = mid -1 => 5 - 1 = 4

Pass 3:
    low = 4
    high = 4

    while(4 <= 4)
        mid = (high - low)/ 2 +low => 4

    if array[4] == target => true
        return 4	

#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) 
    {
        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(4);
    array.push_back(5);
    array.push_back(6);
    array.push_back(7);
    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;
    }

}

4 5 6 7 0 1 2
The target = 0 found at index = 4