SearchInRotatedArray--反转排序数组查找问题

反转的排序数组的查找问题

输入：一个反转的排序数组 + 查找 target
输出：target 的 index / 没有返回-1
要求： O(logn)
用例：[4,5,6,7,0,1,2] + 0 ===> 4

分析

看到 logn 想到分组的思想，找到反转的点，确定目标在这个前还是后。之后查找。提交，Runtime Error。其实可以看到，你这个方法还是O(n)的复杂度。

思路

这个题目是建立在二分查找的基础上的。
首先需要看一下二分法的代码和思想：

int left=0,right=length-1;
while(left<=right){
  int mid = (left+right)/2;
  if(nums[mid]==target) return mid;
  else if(nums[mid]<target) left=mid+1;
  else right=mid-1;
}
return -1;

可以看到二分查找，就是确定三个指针，然后根据每一次的对比调整指针。这里需要明白的是，二分查找是在 有序数组的基础上进行的。这样一来，每一次只需要比较一下 nums[mid] 和 target 的大小关系，就知道 到底是调整 Left 指针还是 right 指针（每次折半的范围）。
但是，这个题目中，由于数组不是有序的。不能直接由比较来确定每一次如何调整相关指针。
具体的做法是： 用 num[mid] 和 num[right] 进行比较，来确定 左半边是有序的还是右半边是有序的。在确定了有序的基础上，判断 target 是否在这个有序的范围内，如果在，把指针向相应的 方向调整即可。

代码

package day_6;

public class SearchInRotatedSortedArray {
    public int search(int[] nums, int target){
        int count = nums.length;
        if(count==0)
            return -1;
        if(count==1)
            if(nums[0]==target)
                return 0;
            else
                return -1;
        int left = 0;
        int right = count-1;

        while (left <= right){  // 高级版的二分查找
            int mid = (left+right)/2;
            System.out.println(mid);
            if(nums[mid]==target)
                return mid;
            else {
            if(nums[mid] < nums[right]) { // 右边有序
                if(nums[mid]<target && nums[right]>=target )
                    left = mid+1;
                else right = mid-1;
            }else{ // 左边有序
                if(nums[mid]>target && nums[left]<= target)
                    right = mid-1;
                else left = mid+1;
                }
            }
        }
        return  -1;
    }

    public  static void main(String[] args){
    int a[] ={1,3};
    SearchInRotatedSortedArray s = new SearchInRotatedSortedArray();
    System.out.print(s.search(a,0));
    }
}