Rotated Sorted Array Search

You are given an integer array 'nums' sorted in ascending order with distinct values. The array may have been rotated at an unknown pivot index 'k' such that the resulting array becomes:

Before rotaion : [ nums[0],nums[1],...,nums[k−1],nums[k],nums[k+1],...,nums[n−1] ]

After rotaion : [ nums[k],nums[k+1],...,nums[n−1],nums[0],nums[1],...,nums[k−1] ]

Example
nums = [5,6,7,8,9,10,11,12] might be rotated at pivot index 3 and become , nums = [8,9,10,11,12,5,6,7]

Task

Given the rotated array 'nums' and an integer 'target', your task is to find the index of 'target' in 'nums'. If 'target' is found, return the index. If 'target' is not found, return -1.

Your algorithm must have a runtime complexity of O(log n).

Input Format

Given the array 'nums' possibly after rotation and an integer 'target'

Constraints

• 1 <= nums.length <= 5000
• -10^4 <= nums[i] <= 10^4
• All values of nums are unique.
• nums is an ascending array that is possibly rotated.
• -10^4 <= target <= 10^4

Output Format

Print the index of the target if it exists in the array 'nums', otherwise return -1.

Sample Input 0

8,9,10,11,12,5,6,7
10

Sample Output 0

2

Sample Input 1

8,9,10,11,12,5,6,7
5

Sample Output 1

5

Sample Input 2

8,9,10,11,12,5,6,7
0

Sample Output 2

-1

Solution

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <sstream>
using namespace std;

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    vector<int> arr;
    string input;
    getline(cin,input);
    stringstream ss(input);
    string substr;

    while (getline(ss, substr, ',')) {
        arr.push_back(stoi(substr));
    }
    int x;
    cin>>x;

    int n=arr.size();
    int high = n-1;
    int low=0;
    while(low<=high){

        int mid = (low + high)/ 2;
        if(x == arr[mid]){
            cout<<mid;
            return 0;
        }
        if(arr[low] <= arr[mid]){
            //search left
            if(arr[low] <= x && x < arr[mid]){
                high = mid - 1;
            }
            else{
                low = mid + 1;
            }
        }
        else{
            if(arr[mid] < x && x <= arr[high]){
                low = mid + 1;
            }
            else{
                high=mid-1;
            }
            //search right
        }


    }



    cout<<-1;
    return 0;
}