搜索旋转数组

搜索旋转数组

1.想法：

如果是拍好序的数组，那么直接使用二分查找进行搜索，现在旋转了后，我们可知至少有两段是有序的，有题意可知复杂度是你的算法时间复杂度必须是 O(log n) 级别。那么就是说一定是将子问题划归为两半进行处理，像二分查找一样。
那么我们观察一下数组结构：，可以发现有如下规律

image.png
无论怎么旋转，至少有一边的顺序和中间值组成的顺序是有序的，例如1,2,3,4,0从1->3是有序的，而从3->0是无序的（且和原问题的结构一样），那么我们可以做出一下结论：
1.如果所搜索的数在有序的数组内，直接使用二分查找，在另一边（可能无序）当做原问题的子问题处理
2.我们需要对target与mid的关系进行分类
image.png

2.代码实现：

public int search(int[] nums, int target) {
         return searchInnums(nums,target,0,nums.length-1);
    }

    private int searchInnums(int[] nums, int target, int start, int end) {
        if(start>end)return -1;
        else{
            int mid = nums[(end-start)/2+start];
            if(mid == target)return (end-start)/2+start;
            if(mid<target){                                      //情况一
                if(nums[end] == target)return end;
                if(nums[end]>mid) {
                    if(nums[end]>target)return MybinarySearch(nums,target,(end-start)/2+start+1,end);//原问题
                    else return searchInnums(nums,target,start,(end-start)/2+start-1);//二分查找
                }else{
                    return searchInnums(nums,target,(end-start)/2+start+1,end-1);
                }
            }else{
                if(nums[start] == target)return start;
                if(nums[start]>mid) {
                    return searchInnums(nums,target,start+1,(end-start)/2+start-1);
                }else{
                    if(nums[start]>target)return searchInnums(nums,target,(end-start)/2+start+1,end);
                    else return MybinarySearch(nums,target,start+1,(end-start)/2+start-1);
                }
            }
        }
    }

    private int MybinarySearch(int[] nums, int target, int start, int end) {
        if(start>end)return -1;
        int mid = nums[(end-start)/2+start];
        if(mid == target)return (end-start)/2+start;
        else if(mid>target) return MybinarySearch(nums,target,start,(end-start)/2+start-1);
        else return MybinarySearch(nums,target,(end-start)/2+start+1,end);
    }

image.png