Search in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Solution: Binary Search

The key idea is to use a slightly modified version of binary search. Before we change the left and right index, we have to check which half is sorted.

It's easy and simple to check which half is sorted, if arr[left] <= arr[mid] then left half is sorted, otherwise right half is sorted.

Then we can verify if the target is located within the sorted range, it not, then it's located in the unsorted part. Thus we update the left and right accordingly.

    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;
            } else if (nums[low] <= nums[mid]) { 
                // left half is sorted
                if (target >= nums[low] && target < nums[mid]) {
                    // target is within the left and mid range
                    high = mid-1;
                } else {
                    // target is located in the right half
                    low = mid + 1;
                }
            } else { 
                // right half is sorted 
                if (target > nums[mid] && target <= nums[high]) {
                    // target is within the mid and right range
                    low = mid + 1;
                } else {
                    // target is located in the left half
                    high = mid - 1;
                }
            }
        }
        return -1;
    }