33.search in rotated sorted array

Problem Statement:¶

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Problem Statement in simple words¶

Given a sorted, rotated array. return the index of target value. approach should work in logn time.

Approach¶

Two pointers low high
check if the array has been rotated more than half -> else if condition
calculate mid and check whether the target exists between low to mid or mid to high range
keep doing until you find the result

Code¶

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int low = 0;
        int high = nums.size() -1;

        while(low <= high){
            int mid = low + (high-low)/2;
            if(nums[mid] == target)
                return mid;
            // the below condition means the array
            // has been rotated more than half
            // 1 2 3 4 5 6 7 
            // 4 5 6 7 1 2 3 <- nums[mid] (7) >= nums[low] (4)
            else if(nums[mid] >= nums[low]){
                // checking if target exists between low and mid
                if(nums[mid] >= target && nums[low] <= target)
                    // mid has already been checked so (mid-1)
                    high = mid - 1;
                else
                    low = mid + 1;
            }else{
                if(nums[mid] <= target && nums[high] >= target)
                    low = mid+1;
                else
                    high = mid-1;
            }
        }

        return -1;
    }
};