题目描述（中等难度）

开始的时候想复杂了，其实就是一个排序好的数组，把前边的若干的个数，一起移动到末尾就行了。然后在 log (n) 下找到给定数字的下标。

总的来说，log（n），我们肯定得用二分的方法了。

解法一

参考这里-Binary-search-solution)首先我们想一下变化前，正常的升序。我们怎么找给定的数字。

我们每次只关心中间位置的值（这一点很重要），也就是上图 3 位置的数值，如果 target 小于 3 位置的值，我们就把 3 4 5 6 抛弃。然后看新的中间的位置，也就是 1 位置的数值。 3 位置， 1 位置的值是多少呢？我们有一个数组。

3 位置的值，刚好就是数组下标为 3 的值，1 位置的值刚好就是下标为 1 的值。

那么如果，按题目要求的，变化后，3 位置 和 1 位置的值怎么求呢？ 此时我们的数组变成下边这样，我们依旧把值从小到大排列。

此时 3 位置的数值对应为数组下标是 0 的值，1 位置的值对应数组下标是 5 的值。任意位置的对应规则是什么呢？0 -> 4, 1 - > 5，4 ->1，就是就是 （位置 + 偏移 ）% 数组的长度。这里就是加上 4 模 7。

问题转换为怎么去求出这个偏移。

我们只要知道任意一个位置对应的数组下标就可以了，为了方便我们可以求位置为 0 的值对应的下标（数组中最小的数对应的下标），0 位置对应的下标就是我们要求的偏移了（0 + 偏移 = 数组下标）。这里 nums = [ 4, 5, 6, 7, 0, 1, 2] ，我们就需要去求数值 0 的下标。

求最小值的下标，因为题目要求时间复杂度是 O（log ( n )），所以我们必须采取二分的方法去找，二分的方法就要保证每次比较后，去掉一半的元素。这里我们去比较中点和端点值的情况，那么是根据中点和起点比较，还是中点和终点比较呢？我们来分析下。

• mid 和 start 比较

  mid > start : 最小值在左半部分。

  

  mid < start： 最小值在左半部分。

  无论大于小于，最小值都在左半部分，所以 mid 和 start 比较是不可取的。

但这样会有一个问题的，对于下边的例子，就会遇到死循环了。

问题出在，当数组剩偶数长度的时候，mid = （start + end）/ 2，mid 取的是左端点。上图的例子， mid > end, 更新 start = mid，start 位置并不会变化。那么下一次 mid 的值也不会变，就死循环了。所以，我们要更新 start = mid + 1。

综上，找最小值的下标的代码就出来了，同时，由于我们找的是位置 0 对应的下标，所以偏移就是最小值的下标。

当然，我们是找最小值对应的下标，然后求出了偏移。我们也可以找最大值的对应的下标，分析思路和之前是一样的，主要还是要注意一下边界的情况，然后就可以求出偏移。

有了偏移，我们就可以愉快的找目标值的数组下标了。

时间复杂度：O（log（n））。

空间复杂度：O（1）。

解法二

参考，题目中的数组，其实是两段有序的数组。例如

[ 4 5 6 7 1 2 3 ] ，[ 4 5 6 7 ] 和 [ 1 2 3 ] 两段有序。

而对于 [ 1 2 3 4] 这种，可以看做 [ 1 2 3 4 ] 和 [ ] 特殊的两段有序。

而对于我们要找的 target ， target 不在的那一段，所有数字可以看做无穷大，这样整个数组就可以看做有序的了，可以用正常的二分法去找 target 了，例如

[ 4 5 6 7 1 2 3] ，如果 target = 5，那么数组可以看做 [ 4 5 6 7 inf inf inf ]。

[ 4 5 6 7 1 2 3] ，如果 target = 2，那么数组可以看做 [ -inf -inf - inf -inf 1 2 3]。

和解法一一样，我们每次只关心 mid 的值，所以 mid 要么就是 nums [ mid ]，要么就是 inf 或者 -inf。

当 nums [ mid ] 和 target 在同一段里边。

• 怎么判断 nums [ mid ] 和 target 在同一段？

  把 nums [ mid ] 和 target 同时与 nums [ 0 ] 比较，如果它俩都大于 nums [ 0 ] 或者都小于 nums [ 0 ]，那么就代表它俩在同一段。例如

  [ 4 5 6 7 1 2 3]，如果 target = 5，此时数组看做 [ 4 5 6 7 inf inf inf ]。nums [ mid ] = 7，target > nums [ 0 ]，nums [ mid ] > nums [ 0 ]，所以它们在同一段 nums [ mid ] = 7，不用变化。

• 怎么判断 nums [ mid ] 和 target 不在同一段？

  把 nums [ mid ] 和 target 同时与 nums [ 0 ] 比较，如果它俩一个大于 nums [ 0 ] 一个小于 nums [ 0 ]，那么就代表它俩不在同一段。例如

  [ 4 5 6 7 1 2 3]，如果 target = 2，此时数组看做 [ - inf - inf - inf - inf 1 2 3]。nums [ mid ] = 7，target < nums [ 0 ]，nums [ mid ] > nums [ 0 ]，一个大于，一个小于，所以它们不在同一段 nums [ mid ] = - inf，变成了负无穷大。

看下代码吧

时间复杂度：O（log（n））。

空间复杂度：O（1）。

解法三

参考这里，算法基于一个事实，数组从任意位置劈开后，至少有一半是有序的，什么意思呢？

比如 [ 4 5 6 7 1 2 3] ，从 7 劈开，左边是 [ 4 5 6 7] 右边是 [ 7 1 2 3]，左边是有序的。

基于这个事实。

我们可以先找到哪一段是有序的 (只要判断端点即可)，然后看 target 在不在这一段里，如果在，那么就把另一半丢弃。如果不在，那么就把这一段丢弃。

时间复杂度：O（log（n））。

空间复杂度：O（1）。

总

三种解法是从不同的思路去理解题意，但本质上都是找到丢弃一半的规则，从而达到 log （n） 的时间复杂度，对二分查找的本质的理解更加深刻了。

添加好友一起进步~

如果觉得有帮助的话，可以点击 给一个 star 哦 ^^