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

Problem explanation:

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 in 2 ways:

1. Linear Search
2. Modified Binary search

1. Linear search:

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

2. Modified Binary search

We can solve this by using a modified binary search.

In Binary search, we divide the sorted array into 2 parts. And change the lower index and higher index according to the mid element.

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 rotating 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;
}

Let us understand with an example

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	

Solution in C++

/*
* File     : search_in_sorted_array.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) 
    {
        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;
    }

}

Output:

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

List Of Tutorials available in this website: