leetcode 33. Search in Rotated Sorted Array

Problems:

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.

解题思路：

一开始我还是使用了传统的mid 与 target 进行比较的方式特别复杂

code:

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

解题思路二：

大神的思路：
对于有序数组，使用二分搜索比较方便。分析题中的数组特点，旋转后初看是乱序数组，但仔细一看其实里面是存在两段有序数组的。刚开始做这道题时可能会去比较 target 和 A[mid] , 但分析起来异常复杂。该题较为巧妙的地方在于如何找出旋转数组中的局部有序数组，并使用二分搜索解之。结合实际数组在纸上分析较为方便。

1.若 target == A[mid] ，索引找到，直接返回
2.寻找局部有序数组，分析 A[mid] 和两段有序的数组特点，由于旋转后前面有序数组最小值都比后面有序数组最大值大。故若 A[start] < A[mid] 成立，则start与mid间的元素必有序（要么是前一段有序数组，要么是后一段有序数组，还有可能是未旋转数组）。
3.接着在有序数组 A[start]~A[mid] 间进行二分搜索，但能在 A[start]~A[mid] 间搜索的前提是 A[start] <= target <= A[mid] 。
4.接着在有序数组 A[mid]~A[end] 间进行二分搜索，注意前提条件。
5.搜索完毕时索引若不是mid或者未满足while循环条件，则测试A[start]或者A[end]是否满足条件。
6.最后若未找到满足条件的索引，则返回-1.

code:

public int search(int[] A, int target) {
        if (A == null || A.length == 0) return -1;

        int lb = 0, ub = A.length - 1;
        while (lb + 1 < ub) {
            int mid = lb + (ub - lb) / 2;
            if (A[mid] == target) return mid;

            if (A[mid] > A[lb]) {
                // case1: numbers between lb and mid are sorted
                if (A[lb] <= target && target <= A[mid]) {
                    ub = mid;
                } else {
                    lb = mid;
                }
            } else {
                // case2: numbers between mid and ub are sorted
                if (A[mid] <= target && target <= A[ub]) {
                    lb = mid;
                } else {
                    ub = mid;
                }
            }
        }

        if (A[lb] == target) {
            return lb;
        } else if (A[ub] == target) {
            return ub;
        }
        return -1;
    }