1.Search in a Sorted Rotated Array

Apply binary search when a array is sorted and rotated.

// Example
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Solution:

class Solution
{
    int binary_search(int target, int start, int end, vector<int> &nums)
    {
        int res = -1;
        while (start <= end)
        {
            int mid = (start + end) / 2;
            if (nums[mid] == target)
            {
                res = mid;
                break;
            }
            else if (target < nums[mid])
            {
                end = mid - 1;
            }
            else
            {
                start = mid + 1;
            }
        }

        return res;
    }

    int find_pivot(vector<int> &nums)
    {

        int pvt = nums.size()-1;

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

public:
    int search(vector<int> &nums, int target)
    {
        if(nums.size()==0){return -1;}
        
        int pvt = find_pivot(nums);
        cout<<pvt;
        int res=0;
        if (target >= nums[0] && target <= nums[pvt])
        {
            int start = 0;
            int end = pvt;
            res = binary_search(target, start, end, nums);
        }
        else
        {
            int start = pvt+1;
            int end = nums.size() - 1;
            res = binary_search(target, start, end, nums);
        }

        return res;
    }
};

Time Complexity: O(log (n)) We have to do two passes to find the element.