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.

Your algorithm's runtime complexity must be in the order of O(log n).

Example 1:

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

Example 2:

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

Solution

class Solution {
    public int search(int[] nums, int target) {
        int low = 0;
        int high = nums.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            int midVal = nums[mid];
            if (target == midVal) {
                return mid;
            }
            int lowVal = nums[low];
            if (midVal < lowVal) { // if middle is less than lowest value
                // 6,7,0,1,2,3,4,5
                if (target < midVal || target >= lowVal) { 
                    // and target is less than middle or target is bigger than lowest value, move high closer to left side (e.g. target=7)
                    high = mid - 1;
                } else {
                    // e.g. target=5
                    low = mid + 1;
                }
            } else {
                // 2,3,4,5,6,7,0,1
                if (target > midVal || target < lowVal) {
                    // target is e.g. 6
                    low = mid + 1;
                } else {
                    // target is e.g. 2
                    high = mid - 1;
                }
            }
        }
        return -1;
    }
}