leetcode81

题目描述

已知存在一个按非降序排列的整数数组 ，数组中可能有重复元素。将数组在预先未知的某个下标 上进行旋转，使数组变为 。给定一个旋转后的数组 和一个整数 ，请你编写一个函数来判断给定的目标值是否存在于数组中，若存在返回 ，否则返回 。

题目分析

这是今天（20200407）力扣的每日一题，就是这样一道看上去就非常简单，几乎可以秒过的题，我却足足做了两个多小时，踩了许多的坑，在此将其记录下来。这道题拿到手我就知道是用二分法做，但是我比较懒，平常很少自己写二分查找的代码，都是直接调 的库函数，所以就想着能不能直接调。注意到二分查找这类库函数的调用的前提就是数组是有序的（有重复元素也没关系，只要保证一直不下降或不上升就行），而这道题给出的数组被分成了两个不下降子序列，所以我的想法就是找到切分点 ，然后根据边界大小判断目标可能在哪个子序列中，随后在其之上调用二分查找库函数就行了。其实目前为止，这样的思路没有任何问题，但问题就出在我找切分点 的方式，我用的是 函数，条件是找到数组中第一个小于 的元素，它的索引就是 。但是整个数组并不是有序的，底层用的也是二分查找的方式，在这里并不满足调用条件。想了好久才明白了这件事，不得不让我感慨， 虽好用，但也要对其底层实现有所了解才行，问题的根源就出在自己对库函数的理解不深刻。

解决

最终还是老老实实地仿照官方题解手写了二分查找的代码，二分查找中特别需要注意的是它的边界情况，搞清楚边界情况该怎么处理，整个程序基本就轻松拿下了。

代码

bool search(vector<int>& nums, int target) {
    int n = nums.size();
    if(n == 0) return false;

    int lp = 0, rp = n - 1;
    while(lp <= rp) {
        int mid = (lp + rp) / 2;
        if(nums[mid] == target) return true;

        // 特殊情况，若不处理可能会误判 mid 所在部分
        if(nums[lp] == nums[mid] && nums[mid] == nums[rp]) {
            lp++; rp--;
        }
        else if(nums[mid] >= nums[lp]) {  // mid 在左半部分；
            if(target >= nums[lp] && target < nums[mid]) rp = mid-1;
            else lp = mid+1;
        }
        else { // mid 在右半部分
            if(target > nums[mid] && target <= nums[rp]) lp = mid+1;
            else rp = mid-1;
        }
    }
    return false;
}