二分专题

发表于 | 更新于 | 评论数： | 阅读次数： | 阅读次数：

二分 ： 存在一种两段性的性质，就可以进行二分（最常见的就是单调性）
流程 ：
1.确定二分边界
2.编写二分框架
3.设计一个check性值
4.判断一下区间如何更新
5.如果更新方式写的是l = mid, r = mid - 1， 那么就在算mid时加上1

1.

1
2
3
int mySqrt(int x) {
    int l = 0, r = x;
}

2.

1
2
3
4
5
6
7
int mySqrt(int x) {
    int l = 0, r = x;

    while (l < r) {
        int mid = l + r >> 1;
    }
}

3.
设t为区间[l, r]中的一个元素， 那么 我们要找到一个t, 他的t * t = x

1
2
3
4
5
6
7
8
9
10
11
int mySqrt(int x) {
  int l = 0, r = x;

    while (l < r) {
        int mid = l + (long long)r + 1>> 1;  //当r是 最大int时， + 1 会溢出， 所以这里转换成long long
        if ( mid <= x / mid ) l = mid;       // mid * mid 可能会溢出
        else
            r = mid - 1;
    }
    return l;
}

…

34. Find First and Last Position of Element in Sorted Array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.empty()) return {-1, -1};
        int l = 0, r = nums.size() - 1;
       
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= target) r = mid;
            else 
                l = mid + 1;
        }
        int start = l; 
        if (nums[l] != target) return {-1, -1};     //二分完成得到的这个点是第一个 >= 8 的点， 不一定 = 8， 所以这里判断一下
        l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (nums[mid] <= target) l = mid;
            else 
                r = mid - 1;
        }
        int end = l;
       
        return {start, end};
    }
};

以[5， 7， 7， 8， 8， 10]为例

  1. 找二段性，按 t >= 8 可以分成两段 （这样划分，二分查找完成后得到的是第一个>= 8 的元素）

if (nums[mid] >= target) 这时， 我们要找的点（第一个 >= 8 的元素）在mid的左边，也可能是mid， 所以 r = mid;

  1. 同理， 我们要找第一个 <= 8的元素， 如果nums[mid] <= 8, 那么此时这个点就在mid的右侧， 也可能是 mid， 所以 l = mid;

74. Search a 2D Matrix

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.size() == 0 || matrix[0].size() == 0) return false;
        int n = matrix.size(), m = matrix[0].size();
        
        int l = 0, r = m * n - 1;
        
        while (l < r) {
            int mid = l + r >> 1;
            if (matrix[mid / m][mid % m] >= target) r = mid;
            else 
                l = mid + 1;
        }
        
        if (matrix[l / m][l % m] != target) return false;
        
        return true;
        
    }
};

n = matrix.size(), m = matrix[0].size()
行号 i = k / m (下取整)
列号 j = k mod m

153. Find Minimum in Rotated Sorted Array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int findMin(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while (l < r)  {
            int mid = l + r >> 1;
            if (nums[mid] < nums.back()) r = mid; //注意这里的 back()
            else 
                l = mid + 1;            
        }
        
        return nums[l];
            
    }
};

back()

返回当前vector容器中末尾元素的引用。

front()

返回当前vector容器中起始元素的引用。

找二段性的位置， 即后半部分满足， 前半部分不满足的——后半部分的元素 小于等于 末尾元素。 结合图片可知， 最小元素即黄色点 就是小于等于 末尾元素的第一个点

278. First Bad Version

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int l = 0, r = n;
        while (l < r) {
            int mid = (long long)l + r >> 1;         // 当 l为最大整数时可能溢出，所以这里强制转化成long long
            if (isBadVersion(mid)) r = mid;
            else
                l = mid + 1;
        }
        
        return l;
    }
};

162. Find Peak Element

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] > nums[mid + 1]) r = mid;
            else 
                l = mid + 1;
        }
        return l;
    }
};

287. Find the Duplicate Number

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int l = 1, r = nums.size() - 1;        //抽屉原理， 对1~n二分
        while (l < r) {
            int mid = l + r >> 1;
            int cnt = 0;
            for (auto x : nums)
                if (x >= l && x <= mid)
                    cnt++;
            if (cnt > mid - l + 1) r = mid;
            else 
                l = mid + 1;
        }
        return l;
    }
};
0%