595cc4a3a3177a40dec105ae2c7304fe
(难度Medium)Problem 33. Search in Rotated Sorted Array(翻转数组查找元素)

链接

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

难度等级

Medium

题干

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).

题意

给定一个数组,这个数组很特殊,它是由一个有序数组翻转得到的。所谓的翻转,是把数组截成两段,然后把这两段调换顺序。

比如数组[0,1,2,4,5,6,7]先分成[0, 1, 2] 和 [4, 5, 6, 7],然后把 [4, 5, 6, 7]放到[0, 1, 2] 的前面,就得到了我们的输入[4,5,6,7,0,1,2]。

要求输入这个数组和一个数字target,返回target在数组当中的位置,如果不存在则返回-1.

注意:需要保证这是一个$O(logN)$的算法。

样例

Example 1:

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

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

题解

刚拿到题目的时候有点蒙,我们根本不知道翻转的位置,怎么查找元素呢?

不过好在题目要求复杂度是$O(logN)$,看似提升了难度,其实也是给了我们提示。既然要是log级的复杂度,那么显然只有二分法一条路。这也是各种比赛以及面试时候的技巧,可以先问问数据量级,基本上一问就能知道算法的复杂度了,有了复杂度其实是一个很大的提示。

好了,现在我们不再是一筹莫展,问题变成了我们应该怎么来二分呢?

解法一 两次二分

我们已经知道需要用二分来解决了,问题的难点只有一个,那就是这个数组有序性不是从头到尾的,中间断过。

那么应该怎么办?当然,第一反应是把这个中断的地方找到,找到之后会发生什么?分析一下就知道,我们可以得到两个有序的串。那么问题就变成了从两个有序的串当中寻找某一个元素的问题。

两个串寻找和一个串寻找是一样的,无非是多找一次罢了。

所以到这里,我们知道,只要找到了这个断点的位置,那么这个问题就解开了。那么,这个断点的位置怎么找呢?很简单,当然还是用二分。

怎么二分呢?

我们可以把这个数组抽象一下,想象成两个坡,大概长成下面这个样子(原谅我丑丑的图):

这个图有点抽象, 大概的意思是左边的一个部分的元素比右边大,并且两个部分都是有序的。

可以知道左侧所有的元素大于右侧所有的元素,那么只要找到左部分最右侧或者右部分最左侧就可以了。

这个二分怎么写呢?

很简单,我们假设左右区间分别是l和r,中间的位置是m。如果nums[m] > nums[l]说明了什么?说明了m一定属于左部分,因为左部分所有的元素大于右部分所有的元素,所以m一定属于左部分。那就l=m,如果nums[m] < nums[l]呢?

说明m一定属于右部分,为什么?因为m> l,如果m属于左部分,那么nums[m] 一定大于nums[l]。所以只要r = m,当l和r足够接近的时候,我们就找到了这个分界的位置。

写成伪代码很简单:

```
def binary_search():
l = 0
r = len(nums)
while r - l > 1:
m = (l + r) / 2
if nums[m] >= nums[l]:
l = m
else:
r = m

top Created with Sketch.