搜索旋转排序数组

原题链接

使用的方法

二分查找

解题思路

• 给定一个整数数组 nums，按照升序排列，数组中的值 不重复。
• 在传递给函数之前，nums 在预先未知的某个下标上进行了 旋转，使数组变为 [4,5,6,7,0,1,2]（假设原数组为 [0,1,2,4,5,6,7]）。
• 请你在数组中搜索 target，如果找到返回其索引，否则返回 -1。
• 由于数组是旋转排序的，我们可以使用二分查找来高效地找到目标值的位置。
• 在二分查找的过程中，我们需要判断当前中间元素所在的区间是有序的还是旋转的。根据中间元素与右边界元素的关系，我们可以确定当前区间是有序的还是旋转的。
• 如果当前区间是有序的，我们可以直接判断目标值是否在这个区间内，如果在，则继续在这个区间内进行二分查找；如果不在，则继续在另一个区间内进行二分查找。
• 如果当前区间是旋转的，我们需要判断目标值是否在这个区间内，如果在，则继续在这个区间内进行二分查找；如果不在，则继续在另一个区间内进行二分查找。
• 通过不断地将搜索范围缩小，我们可以快速地找到目标值的位置或者者确定它不存在于数组中。

代码实现

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        if(n == 0)
            return -1;
        int left = 0, right = n - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid] == target)
                return mid;
            if(nums[mid] < nums[right]){
                // 目标值在右边
                if(target > nums[mid] && target <= nums[right]){
                   left = mid + 1;
                // 目标值在左边
                }else{
                   right = mid - 1;
                }
            } else {
                // 目标值在左边
                if(target >= nums[left] && target < nums[mid]){
                   right = mid - 1;
                // 目标值在右边
                } else {
                    left = mid + 1;
                }
            }
        }
        return -1;
    }
}