本文共 1577 字，大约阅读时间需要 5 分钟。

题目

33. 搜索旋转排序数组
    给你一个升序排列的整数数组 nums ，和一个整数 target 。
    假设按照升序排序的数组在预先未知的某个点上进行了旋转。（例如，数组 [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^4nums 中的每个值都 独一无二nums 肯定会在某个点上旋转-10^4 <= target <= 10^4

题解

1. 暴力搜索法
   一开始我看到这个题目是一个中等难度的题目，所以一开始看题目就不知所以，看不懂题目，然后又仔细看了一遍，感觉这有序无序也没毛关系鸭，直接暴力搜索就可了鸭：

class Solution {
       public int search(int[] nums, int target) {
           for(int i =0;i

结果：

3. 二分搜索
   额，，，让我感到奇怪的地方，为什么条件里面会给这是一个有序数组，并且在某个点进行了旋转，作为一个理科数学难，根据以往惨痛的数学题经验，抱着“题目里给的条件一定有它的用处，不可能用不到”这种感觉，我看了一下此题的评论区，发现很多人说此题的要求时间复杂度为logn（啊，茫然，没有这个要求呀），既然都是要求时间复杂度为logn了，那我们就来做这种解法吧，一般像这种有序啊，然后让你查找某个值的话，而且时间复杂度为logn，这让我们想起了—二分查找，非常符合。

class Solution {
       public int search(int[] nums, int target) {
       int l = 0, h = nums.length - 1, m = 0;    whle (l <= h) {
           m = l + (h - l) / 2;        if (nums[m] == target) {
               return m;        }        // 先根据 nums[m] 与 nums[l] 的关系判断 m 是在左段还是右段         if (nums[m] >= nums[l]) {
               // 再判断 target 是在 m 的左边还是右边，从而调整左右边界 l 和 h            if (target >= nums[l] && target < nums[m]) {
                   h = m - 1;            } else {
                   l = m + 1;            }        } else {
               if (target > nums[m] && target <= nums[h]) {
                   l = m + 1;            } else {
                   h = m - 1;            }        }    }    return -1;}}

结果：

转载地址：http://xwwzi.baihongyu.com/