题目链接

搜索旋转排序数组

题目描述

注意

• nums 按升序排列，数组中的值互不相同
• nums 中的每个值都独一无二
• 题目数据保证 nums 在预先未知的某个下标上进行了旋转

解答思路

• 初始想到二分查找，但是因为本题从某个位置对数组进行了旋转，相当于将数组分成了两段升序排列的数组，所以取中间值将数组分为两段，要先判断某一段是否是有序数组，如果是，再判断目标值是否在该段数组的区间之内，如果在，则在该段有序数组中查找目标值，否则在另一段数组中查找目标值。

代码

class Solution {
    public int search(int[] nums, int target) {
        int res = -1;
        int l = 0;
        int r = nums.length - 1; 
        while(l <= r){
            int mid = (l + r) / 2;
            if(nums[mid] == target){
                //找到最终结果直接跳出
                res = mid;
                break;
            }
            //已经找到最接近目标值的一个数
            if(l == r){
                break;
            }
            //左侧数组有序
            if(mid != l && nums[mid - 1] >= nums[l]){
                if(nums[l] <= target && target <= nums[mid - 1]){
                    r = mid - 1;
                }else{
                    l = mid + 1;
                }
            }
            //右侧数组有序(注意左侧数组有序时，右侧数组仍然可能有序，只需要判断一次即可)
            else if(mid != r && nums[mid + 1] <= nums[r]){
                if(nums[mid + 1] <= target && target <= nums[r]){
                    l = mid + 1;
                }else{
                    r = mid - 1;
                }
            }
        }
        return res;
    }
}

关键点

• 先判断某一段数组是否是有序数组，如果有序再判断目标值是否在该段数组区间之内
• 注意：某段数组如果不是有序数组，则另一段数组必定是有序数组；但是如果某段数组如果是有序数组，另一段数组未必不是有序数组，所以在判断时，只需要判断一次有序数组即可，找到有序数组就可以确定目标值应该在哪一段数组中查找