二分变种

发表于 更新于 本文字数： 547 阅读时长 ≈ 2 分钟

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];
    }
};