二分变种

Posted on Edited on Symbols count in article: 1.6k Reading time ≈ 1 mins.

540 有序数组中的单一元素

我的二分

  • 与右侧配对失败:
    • 右侧是奇数: l = m + 1
    • 右侧是偶数: r = m
  • 与右侧配对成功:
    • 右侧是奇数: l = m + 2
    • 右侧是偶数: r = m - 1 
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      class Solution {
      public:
          int singleNonDuplicate(vector<int>& nums) {
              int l = 0, r = nums.size()-1;
              while(l < r){ // 这样可以放心取m+1不越界
                  int m = (l + r) >> 1;
                  if(nums[m] != nums[m+1]){
                      if((r-m) & 1) l = m + 1;
                      else r = m;
                  }else{
                      if((r-m-1) & 1) l = m + 2;
                      else r = m - 1;
                  }
              }
              return nums[l];
          }
      };

官方的全数组二分查找

  • 假设要找的是数字X，则在X左边的数，下标是偶数的都是重复数字的第一位，下标是奇数的都是重复数字的第二位；在X右边的数，下标是奇数的都是重复数字的第一位，下标是偶数的都是重复数字的第二位；

  • 取中值时，若m是偶数，则尝试与m+1比较是否相等，相等则表明[:m+1]正常，X在m+1的右侧，因此l = m + 2；若不相等，则X在[:m]，因此r = m

  • 取中值时，若m是奇数，则尝试与m-1比较是否相等，相等则表明[:m]正常，X在m的右侧，因此l = m + 1；若不相等，则X在[:m]，因此r = m 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Solution {
    public:
        int singleNonDuplicate(vector<int>& nums) {
            int l = 0, r = nums.size() - 1;
            while (l < r) {
                int m = (l + r) >> 1;
                if((m & 1) && nums[m] == nums[m-1]){ // 奇数
                    l = m + 1;
                }else if(!(m & 1) && nums[m] == nums[m+1]){ // 偶数
                    l = m + 2;
                }else{
                    r = m;
                }
            }
            return nums[l];
        }
    };

  • 上述思想可以在代码层面进行简化m ^ 1，对于偶数表示m + 1；对于奇数表示m - 1，同时照顾到短板，每次更新l时，有l = m + 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int m = (l + r) >> 1;
            if (nums[m] == nums[m ^ 1]) { // 这是技巧
                l = m + 1;
            }else{
                r = m;
            }
        }
        return nums[l];
    }
};

官方的偶数范围二分查找

  • X的下标一定是偶数 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class Solution {
    public:
        int singleNonDuplicate(vector<int>& nums) {
            int l = 0, r = nums.size()-1;
            while (l < r) {
                int m = (r - l) / 2 + l;
                m -= m & 1; // 变为偶数
                if (nums[m] == nums[m + 1]) { // [...m+1]都ok
                    l = m + 2;
                } else {
                    r = m;
                }
            }
            return nums[l];
        }
    };