#include <iostream>
#include <vector>

using namespace std;

int binarySearch(vector<int>& nums, int s, int e, int target){
    int start = s;
    int end = e;
     
    int mid = start + (end-start)/2;
    while(start <= end){
        if(target == nums[mid]){
            return mid;
        }
        else if(target < nums[mid]){
            end = mid-1;
        }else{
            start = mid+1;
        }
        mid = start + (end-start)/2;
    }
    return -1;
}

int findPivot(vector<int>& nums){
    int start = 0;
    int end = nums.size()-1;
    
    int mid = start + (end-start)/2;
    while(start < end){
        if(nums[mid] >= nums[0]){
            start = mid+1;
        }else{
            end = mid;
        }
        mid = start + (end-start)/2;
    }
    return mid;
}

int main() {
    vector<int> nums{ 4, 5, 6, 7, 0, 1, 2 };
    int target = 0;
    
    int pivot = findPivot(nums);
    int start = 0;
    int end = nums.size() - 1;
    
    if(target >= nums[pivot] && target <= nums[end]){
        start = pivot;
    }else{
        end = pivot-1;
    }
    
    int res = binarySearch(nums, start, end, target);
    cout << "Index of Target : " << res << endl;
    
    return 0;
}