搜索旋转数组

升序排列的整数数组 nums 在预先未知的某个点上进行了旋转（例如， [0,1,2,4,5,6,7] 经旋转后可能变为 [4,5,6,7,0,1,2] ）。

请你在数组中搜索 target ，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0

输出：4
示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

示例 3：
输入：nums = [1], target = 0
输出：-1

提示：
1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
nums 中的每个值都 独一无二
nums 肯定会在某个点上旋转
-10^4 <= target <= 10^4
通过次数207,686提交次数517,680

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

先判断nums[mid]和nums[r]的大小关系

• 如果nums[mid]==target 直接返回

• 如果nums[mid]<nums[r]那么右半边是有序的

  对于右半边的如果nums[mid] < target && target <= nums[r]那么在右半边，否则在左半边

• 如果nums[mid]>nums[r]那么左半边是有序的

  对于左半边的如果nus[mid] > target && target >= nums[l]那么在左半边，否则在右半边

• 否则存在重复数字，需要一点点移动

class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) return -1;
        int l = 0, r = nums.length - 1, mid = 0;

        while (l <= r) {
            mid = l + (r - l) / 2;

            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < nums[r]) {                       //右半部分是有序的

                if (nums[mid] < target && target <= nums[r]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }

            } else if (nums[mid] > nums[r]) {                       //左半部分是有序的

                if (target < nums[mid] && target >= nums[l]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }

            } else {
                r--;
            }
        }

        return -1;
    }
}

赏

谢谢你请我吃糖果

微信