【LeetCode题意分析&解答】33. Search in Rotated Sorted Array

Suppose a sorted array 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.

题意分析:

  本题是将一个排好序的数组从某一个(不清楚为什么原题中是some pivot,但是肯定是一个,因为如果是多个,考虑极端情况数组将会变成完全是无序的)位置进行旋转,也就是说将一个本来严格递增的数组变成了前后两部分递增的序列,所以会有一个分界。在这样一个旋转后的数组里面查找数字,并返回它的下标,如果找不到的话返回-1。

解答:

如果是个普通的递增数组,那么直接用二分查找就ok了。本题并不是一个严格递增的序列,但是仍然可以用二分查找去做。

二分查找的核心是取两端元素的中间节点mid,本题可以在获取了mid之后和两端元素对比。如果左边元素小于mid,那么mid一定是落在了右面的递增序列中;反之一定是落在了左边。target是要查找的值,知道了mid在哪边之后,就可以拿边界值和target做对比得到两种特殊情况:

  1. 落在右端时,如果target大于右端最大值,那么要查找的一定在左端;
  2. 落在左端时,如果target小于左端最小值,那么要查找的一定在右端。

除去这两种特殊情况之后,直接简单的用二分查找进行处理就可以了。

AC代码:

class Solution(object):
def search(self, nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) / 2
if nums[mid] == target:
return mid
# mid in the right side of rotated sorted array
if nums[left] > nums[mid]:
# target can't be in the right side
if target > nums[right]:
right = mid - 1
else:
# simple binary search
if nums[mid] > target:
right = mid - 1
else:
left = mid + 1
# mid in the left side of rotated sorted array
else:
# target can't be in the left side
if target < nums[left]:
left = mid + 1
else:
if nums[mid] > target:
right = mid - 1
else:
left = mid + 1
return -1
上一篇:python 实现google authenticator 认证


下一篇:Binary Tree Postorder Traversal