33. Search in Rotated Sorted Array

发表于 | 分类于

每日一题 2019 - 03 - 24

题目：

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm’s runtime complexity must be in the order of O(log n).

Example 1:

1
2
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

1
2
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

解法：

这个题让我们找出某个数字在数组中的位置，这个数组是按升序排好的但是从中间某个地方反折过，且要求时间复杂度为o(logn)​；

思路为二分查找的改变，从中间元素查起：

  • 如果中间元素小于末尾元素，那证明从中间到最后元素是正常升序，在这种情况下
    • 如果中间元素小于目标元素且最右边元素大于目标元素，那证明我们要找的元素位于这个序列之间
    • 否则的话，我们需要将 right 指针移到mid左边一位
  • 如果中间元素大于末尾元素，那证明从中间到最后元素存在反折现象，在这种情况下
    • 如果中间元素大于目标元素且最左边元素小于目标元素，那证明我们要找的元素位于这个序列之间
    • 否则的话，我们需要将 left 指针移到mid右边一位

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if ( nums[mid] == target) return mid;
            else if ( nums[mid] <  nums[right]) {
                if ( nums[mid] < target &&  nums[right] >= target) left = mid + 1;
                else right = mid - 1;
            } else {
                if ( nums[left] <= target &&  nums[mid] > target) right = mid - 1;
                else left = mid + 1;
            }
        }
        return -1;
    }
};
0%
undefined