33. Search in Rotated Sorted Array

Medium

这个解法比之前我会的那个先找最小值的解法代码少，但我不是很明白why it works thought I know what the code did.

class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0){
            return -1;
        }
        int start = 0;
        int end = nums.length - 1;
        while (start + 1 < end){
            int mid = start + (end - start) / 2;
            if (nums[mid] == target){
                return mid;
            } else if (nums[mid] > nums[end]){
                if (target >= nums[start] && target <= nums[mid]){
                    end = mid;
                } else {
                    start = mid;
                }
            } else if (nums[mid] < nums[end]){
                if (target >= nums[mid] && target <= nums[end]){
                    start = mid;
                } else {
                    end = mid;
                }
            }
        }
        if (nums[start] == target){
            return start;
        }
        if (nums[end] == target){
            return end;
        }
        return -1;
    }
}

之前那个方法：记得有一个地方就是当target比最后一个array element大的时候，如果算出来的smallest( the first element <= last array element)是0，也就是没有rotate过，那我们的target居然比最大的还大，肯定是找不到这个target的，这个edge case返回-1.

class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0){
            return -1;
        }
        int start = 0;
        int end = nums.length - 1;
        int smallest = -1;
        while (start + 1 < end){
            int mid = start + (end - start) / 2;
            if (nums[mid] > nums[end]){
                start = mid;
            } else if (nums[mid] <= nums[end]){
                end = mid;
            }
        }
        if (nums[start] < nums[nums.length - 1]){
            smallest = start;
        }else {
            smallest = end;
        }
        if (target > nums[nums.length - 1]){
            if (smallest == 0){
                return -1;
            }
            start = 0;
            end = smallest - 1;
            while (start + 1 < end){
                int mid = start + (end - start) / 2;
                if (nums[mid] > target){
                    end = mid;
                } else if (nums[mid] <= target){
                    start = mid;
                }
            }
            if (nums[start] == target){
                return start;
            } else if (nums[end] == target){
                return end;
            } 
            return -1;
            
        } else {
            start = smallest;
            end = nums.length - 1;
            while (start + 1 < end){
                int mid = start + (end - start) / 2;
                if (nums[mid] > target){
                    end = mid;
                } else if (nums[mid] <= target){
                    start = mid;
                }
            }
            if (nums[start] == target){
                return start;
            } else if (nums[end] == target){
                return end;
            } 
            return -1;
        }
    }
}