LeetCode33旋转排序数组的二分查找

Search in Rotated Sorted Array

描述

假设有一个排序好的数组，然后根据一个pivot进行了旋转，比如[1,2,3,4,5,6,7,8] -> [6,7,8,1,2,3,4,5]。
你的任务是从旋转后的数组中找到一个数字的下标，比如6的下标为1,而如果不存在这个数则返回-1。
要求：时间复杂度O(log(n))

解法

• 显然看到了logn就应该想到分而治之(Divide and Conquer)。如何使用D&C有三种方法
  • 1. 这题最简单的做法， 就是通过分而治之先找到上面提到的pivot，“旋转”回去，然后再去看有没有这个数。
  • 2. 根据“旋转”特性，会发现这个数组除了某个地方发生了阶跃，其他的都是递增的。那么不管Mid在哪，总有一边(left->mid , mid->right)是单调递增的。这样我们总是可以根据递增边判断mid和target的关系与位置。
  • 3. 对2方法进一步总结改进的方法，nums[0]<=target, target<=nums[i], nums[i]<nums[0]三个条件包含了所有情况，然后通过异或写了一个简洁的方法：https://leetcode-cn.com/problems/search-in-rotated-sorted-array/solution/ji-jian-solution-by-lukelee/

边界条件

• 很显然，上面的思想想到还是不难的，至少可以做到第二步思想，但是边界条件，还是需要在思考一下。
• 二分查找算法的边界,一般来说分两种情况,一种是左闭右开区间,类似于[left, right),一种是左闭右闭区间,类似于[left, right].需要注意的是, 循环体外的初始化条件,与循环体内的迭代步骤, 都必须遵守一致的区间规则。
• 编程珠玑给出的最佳方法：

int search4(int array[], int n, int v)
{
int left, right, middle;

left = -1, right = n;

while (left + 1 != right)
{
    middle = left + （right － left) / 2;

    if (array[middle] < v)
    {
        left = middle;
    }
    else
    {
        right = middle;
    }
}

if (right >= n || array[right] != v)
{
    right = -1;
}

return right;
}

参考：https://blog.csdn.net/weixin_43705457/article/details/87874779