33. 搜索旋转排序数组

33. 搜索旋转排序数组 - 力扣（LeetCode）

class Solution {
public:
  int search(vector<int>& nums, int target) {
    int L = 0, R = nums.size() - 1;
    while (L <= R) {
      int M = (L + R) / 2;
      int NL = nums[L], NR = nums[R], NM = nums[M];
      if (target == NM)
        return M;

      if (NL <= NM) {
        if (NL <= target && target < NM)
          R = M - 1;
        else
          L = M + 1;
      } else {
        if (NM < target && target <= NR)
          L = M + 1;
        else
          R = M - 1;
      }
    }
    return -1;
  }
};

这个说实话，二刷的时候还是要好好看看二分。这些乱七八糟的大于小于号之类的边界条件太难搞了。我上面这个答案是根据这个评论来的，我感觉算是最容易理解的。

注意，找有序数组的目的在于：我们需要根据有序部来判断 target 的位置。这也正是为什么这里两层 if 的条件语句方向是相同的，可以用这个方法来辅助记忆。

二刷

class Solution {
public:
  int search(vector<int>& nums, int target) {
    int L = 0, R = nums.size();
    while (L != R) {
      int M = (L + R) / 2;
      if (nums[M] == target)
        return M;
      if (nums[L] < nums[M]) {
        // Intuitively, search using the ordered subzone.
        if (nums[L] <= target && target < nums[M])
          R = M;
        else
          L = M + 1;
      } else {
        // However, this is really mindblowing... Seems that searchability
        // doesn't really need the subzone to be ordered.
        // XXX The following clause won't work since R is past the last element.
        // if (nums[M] < target && target <= nums[R])
        if (nums[L] <= target || target < nums[M])
          R = M;
        else
          L = M + 1;
      }
    }
    return -1;
  }
};

我第二次写出来这个解法说实话有点震惊到我了……这个题目的直观思路是「根据有序段来判定应该向哪里去」——这个方法本身完全没问题，事实上我的最外层第一个分支 nums[L] < nums[M] 发现左侧有序之后，下面也就立刻判定了 target 是不是在有序段之内；

但是，但是，如果进入了外层第二个分支，也就是右侧段有序的话，再按照相同的思路判断右侧段，会发生经典的 off-by-one 问题——R 是在最后一个元素之后的。那该怎么办？我服了，我鬼迷心窍地写了一个在非有序段搜索，结果竟然还真管用？！

事实上你也可以发现，nums[M] < target && target <= nums[R] 和 nums[L] <= target || target < nums[M] 是一组互补的事件，它们隐含在各自的 else 分支当中。我只能说这太疯狂了，我没话说了，真的。

而且采用了 C++ 迭代器式写法的话，你会发现对 L、M、R 三者的范围和变化判断会变得非常非常直观。这种写法完全是正确的，就应该这么写。

三刷

class Solution {
public:
  int search(vector<int>& nums, int target) {
    int L = 0, R = nums.size();
    while (L != R) {
      int M = L + (R - L) / 2;
      if (target == nums[M])
        return M;

      // Determine ordered zone first.
      if (nums[L] < nums[M]) {
        // Ordered zone at left.
        if (nums[L] <= target && target < nums[M])
          R = M;
        else
          L = M + 1;
      } else {
        // Ordered zone at right.
        if (nums[L] <= target || target < nums[M])
          R = M;
        else
          L = M + 1;
      }
    }
    return -1;
  }
};

注意，做这道题的逻辑是首先考虑有序区间，然后再考虑target分属哪个区间。所以下面这种做法是错的，吃力不讨好：

if (target < nums[M]) {
  if (nums[L] < target)
    R = M;
   else
    L = M + 1;
} else {
  if (nums[L] < target)
    L = M + 1;
  else
    R = M;
}

然后上面这种写法能起作用的analogy还是在于有序序列旋转后有连续性、断裂性，也就是

（待补图）