33-搜索旋转排序数组

Leetcode题解
  1. 33、搜索旋转排序数组
    1. 题目：
    2. 题解：

33、搜索旋转排序数组

题目：

https://leetcode-cn.com/problems/search-in-rotated-sorted-array/

UfAyod.png

旋转排序数组，即将一个升序的数组一部分调转到一边。此题要求在一个旋转排序数组中寻找target的索引值，并且要求时间复杂度是O(logn)，很明显要进行二分法查询。此题与普通的二分法查询不同在于是旋转排序数组，但其实经过分析，得出旋转数组的特性：在一个旋转数组中，一个区间[i,j]，如果nums[i] <= nums[j]，一定说明[i,j]是连续递增的。

因此，编码逻辑为：

初始l = 0， r = n - 1，mid = (l + r) / 2；

若 target == nums[mid]，直接返回

如果nums[l] <= nums[mid] ，且nums[l] <= target < nums[mid]，则target就在此时的左半部分r=mid-1，否则target在右半部分l=mid+1。

如果nums[mid]<=nums[r]，且nums[mid] < target <= nums[right],则target就在此时的右半部分l=mid+1，否则target在左半部分r=mid-1。

一个特别的二分查找，编码中的判断尽量减少类似mid-1的语句，一些特殊的输入案例会直接导致堆栈溢出。例如nums[mid-1] >= target替换为nums[mid]>target

题解：

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
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        if (n == 0)
            return -1;
        if (n == 1)
            return nums[0] == target ? 0 : -1;
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if(nums[mid] == target)
                return mid;
            if(nums[l] <= nums[mid]) {
                if (nums[l] <= target && nums[mid] > target) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                if(nums[mid] < target && nums[r] >= target) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
         }
        return -1;
    }
};

当前网速较慢或者你使用的浏览器不支持博客特定功能，请尝试刷新或换用Chrome、Firefox等现代浏览器