33. 搜索旋转排序数组(中等)

Posted on In Views:

1，问题描述

33. 搜索旋转排序数组

难度：中等

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

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

示例 2：

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

示例 3：

1
2
输入：nums = [1], target = 0
输出：-1

提示：

  • 1 <= nums.length <= 5000
  • -104 <= nums[i] <= 104
  • nums 中的每个值都 独一无二
  • 题目数据保证 nums 在预先未知的某个下标上进行了旋转
  • -104 <= target <= 104

2，初步思考

​ 有序！要求时间复杂度为O(logn)！查找一个目标数字！

​ 这些提示都已经把要使用的方法直接说出来了，只能是二分查找法啊！

​ 需要特别注意的是二分查找时必然有一半是有序的，利用有序的那一半去做检查和处理！

3，代码处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public class _33搜索旋转排序数组 {
    // 解法：2分查找法，因为有时间复杂度O(logn)的要求，那么必然是二分查找法
    // 想办法模拟适配这个结构的二分查找法
    // 左右两侧不是最大值！！
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        if (nums[left] == target) return left;
        if (nums[right] == target) return right;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) return mid;
            int cur = nums[mid];
            if (nums[left] <= cur) {// 左半边有序
                if (nums[left] <= target && target <= cur) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {// 右半边有序
                if (cur <= target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        _33搜索旋转排序数组 searchRotateArray = new _33搜索旋转排序数组();
        System.out.println(searchRotateArray.search(new int[]{4, 5, 6, 7, 0, 1, 2}, 0));
        System.out.println(searchRotateArray.search(new int[]{4, 5, 6, 7, 0, 1, 2}, 3));
        System.out.println(searchRotateArray.search(new int[]{5, 1, 3}, 3));
        System.out.println(searchRotateArray.search(new int[]{5, 1, 2, 3, 4}, 2));
        System.out.println(searchRotateArray.search(new int[]{4, 5, 6, 7, 8, 1, 2, 3}, 8));
        System.out.println(searchRotateArray.search(new int[]{4, 5, 6, 7, 0, 1, 2}, 0));
        System.out.println(searchRotateArray.search(new int[]{4, 5, 6, 7, 8, 1, 2, 3}, 8));

    }
}
/**
 * ,6,7,0,1,2,4,5: 3
 */