问题描述

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.

这道题是前段时间在百度实习生面试的时候的一道题，当场面试的时候没有想明白，然后就挂在了这个题目上。。 今天在Leetcode上看到这个题，总结了一下思路。 面试的时候直接提出，找到分割点，这个问题就转换为简单的二分搜索问题。结果面试官说不行，Orz。。直接上来就要二分搜索。 好吧，上来如何二分搜索呢： 我们采用如下图表示该数组，长度越长表示数字越大。

数组图

left, right分别表示两端边界，mid为中间元素。 情况主要分以下几种：

  1. nums[mid] >= nums[left] 数组图

这种时候，我们可以看到，在left到mid之间必然是一个升序数组，所以我们就比较target和mid

  • target > nums[mid] 说明target在mid+1和right之间， left = mid + 1
  • target <= nums[mid] 时，需要进一步比较target和right的值。
    • target < nums[mid] ，说明target在右半部分，left = mid + 1
    • 否则在左半部分，right = mid - 1
  1. nums[mid]< nums[left] 数组图

这个时候，我们必然可以得出mid到right之间是一个升序的数组，同理

  • target < nums[mid], 说明目标数字在left到mid之间，直接left = mid + 1
  • target >= nums[mid],需要进一步比较：
    • target < nums[mid]时，说明target在右半部分，left = mid + 1
    • 否则，right = mid - 1

代码见我的Github 我并没有对逻辑进行简化，如果对逻辑进行简化的话会更简单。脑子还是不够灵活啊。。

希望你喜欢。