lcBinarySearch - 二分搜索

Posted on Edited on

0 二分搜索以及实现

我们把普通人的实现：在递增数组里面，搜索target：
最后一定是通过st+=1，使得st == ed然后退出循环，所以我们知道，下面的二分找到的一定是第一个 >= target的值，这也是lower_bound的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ed = peakIdx, st = 0; 
int mid;
while(st < ed) {
    mid = (st + ed) >> 1;
    int h = mountainArr.get(mid);
    if(h < target) { // 注意最后的收敛一定是st += 1去收敛的
        st = mid + 1;
    } else {
        ed = mid;
    }
}
if(mountainArr.get(st) == target) {
    return st;
}
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// lower_bound函数的实现： ------------------------------------------
template<class ForwardIt, class T>
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value)
{
    ForwardIt it;
    typename std::iterator_traits<ForwardIt>::difference_type count, step;
    count = std::distance(first, last);
 
    while (count > 0) {
        it = first; // st 
        step = count / 2; // mid 
        std::advance(it, step); // vec[mid]
        if (*it < value) { // vec[mid] < value
            first = ++it;  // st = mid + 1
            count -= step + 1; // ed mot move, but st move forward，so move count backward
        }
        else
            count = step; // ed = mid
    }
    return first;
}

// upper_bound函数的实现： ------------------------------------------
// 看到!(value < *it) 也就是 value >= *it 
// 这就是说，当*it小于等于目标，那么st++，也就是找到的数为第一个大于value的值
template<class ForwardIt, class T>
ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value)
{
    ForwardIt it;
    typename std::iterator_traits<ForwardIt>::difference_type count, step;
    count = std::distance(first, last);
 
    while (count > 0) {
        it = first; 
        step = count / 2; 
        std::advance(it, step);
        if (!(value < *it)) {
            first = ++it;
            count -= step + 1;
        } 
        else
            count = step;
    }
    return first;
}

1 例题

1157majorityChecker 子数组中占绝大多数的元素

1 题目

https://leetcode.cn/problems/online-majority-element-in-subarray/

2 解题思路

  • 1 解题思路：
    • 1.1 首先统计所有元素的下标
    • 1.2 对于l,r,thres的一个搜索，对所有元素遍历，找出第一个满足要求的元素返回即可：
      • 1.2.1 首先该元素的个数要大于等于thres
      • 1.2.2 在该元素的出现下标的列表中二分搜索，找到第一个大于等于l的下标，和第一个大于r的下标，分别对应到lower_bound和upper_bound
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
27
28
29
30
class MajorityChecker {
public:
    vector<int> vec;
    unordered_map<int, vector<int>> toPos;
    MajorityChecker(vector<int>& arr) {
        int pos = 0;
        for(auto& num : arr) {
            toPos[num].push_back(pos++);;
        }
    }
    
    int query(int left, int right, int threshold) {
        int res = -1;
        for(auto& [num, positions] : toPos) {
            if(positions.size() < threshold) {
                continue;
            }
            // for num : find the min and max pos in [left, right]
            auto minPos = lower_bound(positions.begin(), positions.end(), left);
            auto maxPos = upper_bound(positions.begin(), positions.end(), right);
            if (maxPos - minPos >= threshold) {
                return num;
            }
        }

        return res;
        
    }
};

1095findInMountainArray 山脉数组中查找目标值

1 题目

https://leetcode.cn/problems/find-in-mountain-array/

2 解题思路

  • 1 解题思路：
    • 1.1 二分法：首先找到山顶，接着在两边分别二分找target就行 
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
public:
    int findInMountainArray(int target, MountainArray &mountainArr) {
        int len = mountainArr.length();
        int ed = len-1, st = 0; 
        int peakIdx;
        while(st < ed) {
            peakIdx = (st + ed) >> 1;
            // cout << "st/ed/mid: " << st << " " << ed << " " << peakIdx << endl;
            int h = mountainArr.get(peakIdx);
            int lh = mountainArr.get(peakIdx - 1);
            int rh = mountainArr.get(peakIdx + 1);
            if(lh < h && h < rh) {
                st = peakIdx + 1;
            } else if(lh > h && h > rh){
                ed = peakIdx;
            } else {
                st = peakIdx;
                break;
            }
        }
        peakIdx = st;
        // cout << "peak is : " << st << "  " << mountainArr.get(st) <<endl;
        
        ed = peakIdx, st = 0; 
        int mid;
        while(st < ed) {
            mid = (st + ed) >> 1;
            int h = mountainArr.get(mid);
            if(h < target) {
                st = mid + 1;
            } else {
                ed = mid;
            }
        }
        if(mountainArr.get(st) == target) {
            return st;
        }

        ed = len-1, st = peakIdx; 
        while(st < ed) {
            mid = (st + ed) >> 1;
            int h = mountainArr.get(mid);
            if(h > target) {
                st = mid + 1;
            } else {
                ed = mid;
            }
        }
        if(mountainArr.get(st) == target) {
            return st;
        }

        return -1;
    }
};

0878nthMagicalNumber 第 N 个神奇数字

1 题目

https://leetcode.cn/problems/nth-magical-number/

2 解题思路

  • 1 解题思路：
    • 1.1 经典二分：并不是遍历去搜索，而是在答案的范围内，去二分，对于每各数字判断它和最终要的结果的大小，决定下一个二分的范围
    • 1.2 具体来说，比如这道题：f(x)表示数字x是第几个magicnumber，很容易知道f(x)单调递增，则可以二分
    • 1.3 f(x) = x/a + x/b - x/LCM(a,b)
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
    long long getLCM(long long x, long long y) {
        return x * y / getGCD(x, y);
    }
    
    long long getGCD(long long x, long long y) {
        long long l = min(x, y);
        long long g = max(x, y);
        long long mod = g % l;
        while(mod != 0) {
            g = l;
            l = mod;
            mod = g % l;
        }
        return l;
    }
    
    constexpr static int MOD = 1'000'000'007;

    int nthMagicalNumber(int n, int a, int b) {
        long long lcm = getLCM(a, b);
        auto getMagicRank = [&](long long x) {
            return x / a + x / b - x / lcm;
        };
        long long st = 0;
        long long ed = 1e15;

        long long mid = -1;
        while(st != ed) {
            mid = (st + ed) >> 1;
            
            long long rank = getMagicRank(mid);
            // cout << "st/ed/mid: " << st << "/" << ed << "/" << mid << " | " << rank << endl;
            if(rank >= n) {
                ed = mid;
            } else {
                st = mid + 1;
            }
        }

        return st % MOD;
    }
};

0668findKthNumber 乘法表中第k小的数

1 题目

https://leetcode.cn/problems/kth-smallest-number-in-multiplication-table/

2 解题思路

  • 1 解题思路：
    • 1.1 找乘法表中的第k个数字，应该考虑在1到m*n中，找一个最小的数字mid，小于等于mid的数字，刚好有k个
    • 1.2 为何能够保证，比如对于3*3的乘法表展开：（12233 4669），找的是第7个或者第8个数字，那么二分搜索的过程如下：
    • 1.3 从过程中可以发现，当目前的mid满足了大于等于k个的时候，每次ed = mid，下一个mid就会减小，比如从st/ed的6,9变成6,7,最后搜索到6，也就是，找一个最小的数字，乘法表中有k个小于等于他，最后一定会搜索到它，我们可以反证法：
    • 1.4 假设从1到m*n，找到一个数字有k个小于等于他，记作x，他出现在这个乘法表中，假设它不是最小的，那么也就是说存在一个数字y，y < x出现在乘法表中，且有k个数字小于等于他，很显然是错的，因为这样x，就至少是有k+1个数字小于等于他，和前提相反！
    • st/ed/cnt: 1/9/6 | 5
      st/ed/cnt: 6/9/8 | 7
      st/ed/cnt: 6/7/8 | 6
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:
    int findKthNumber(int m, int n, int k) {
        // 对于每一个数字x，他在乘法表中是多大的？
        // 那么求解方案就变成了：
        // 找到最小的数字，这个数字有k个小于等于他
        int st = 1, ed = m*n, mid;
        while(st != ed) {
            // 小于等于mid的个数为cnt
            mid = (st + ed) >> 1;
            int cnt = 0;
            for(int line = 1; line <= m; ++line) {
                cnt += min(mid / line, n);
            }
            
            cout << "st/ed/cnt: " << st << "/" << ed << "/" << cnt << " | " << mid  << endl;
            if(cnt >= k) {
                ed = mid;
            } else {
                st = mid + 1;
            }
        }
        return st;

    }
};

0004findMedianSortedArrays 寻找两个正序数组的中位数

1 题目

https://leetcode.cn/problems/median-of-two-sorted-arrays/

2 解题思路

  • 1 解题思路：
    • 1.1 将直接二分找目标数的思路转换一下，找两个数组中第k大的数字
    • 1.2 那么通过比较 A[k/2 - 1]和B[k/2 - 1]这两个数字，我们能发现，在这两个数字左侧（不包含这两个数字）最多有k - 2个，这样最答案一定不在前面的AB段里面，可以去掉A的或者B的[:k/2 - 1]这个部分的数字，然后更新k(k代表着我们还要去掉多少个数字)，同时更新stA和stB标记AB的起点
    • 1.3 退出的过程：当 1 = k的时候，意味着从AB当前的起点，仅需要找一个数字即可，那么自然是两个的最小值
    • 1.4 考虑，肯定会出现A或者B的下标溢出情况，那么由于我们知道还有多少个数字要数，那么直接在另一个不溢出的数组里返回结果即可！
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
public:
    int getKthElement(vector<int>& nums1, vector<int>& nums2, int k) {
        // cout <<"------------" << endl;
        int idx1 = k / 2 - 1;
        int m = nums1.size();
        int n = nums2.size();
        int st1 = 0;
        int st2 = 0;

        while(true) {
            // 当k消耗殆尽，则直接返回结果
            // cout << "m/n" << m << " " << n << endl;
            if(st1 == m) {
                // cout <<"aa" << endl;
                return nums2[st2 + k - 1];
            }
            if(st2 == n) {
                return nums1[st1 + k - 1];
            }
            if(k == 1) {
                // cout << st1 << " | " << st2 << endl;
                return min(nums1[st1], nums2[st2]);
            }

            int nextSt1 = min(st1 + k / 2 - 1, m - 1);
            int nextSt2 = min(st2 + k / 2 - 1, n - 1);
            if(nums1[nextSt1] > nums2[nextSt2]) {
                k = k - (nextSt2 + 1 - st2); // 排除了这么些个数字
                st2 = nextSt2 + 1;
                // cout << "st2: " << st2 << endl;
            } else {
                k = k - (nextSt1 + 1 - st1);
                st1 = nextSt1 + 1;
                // cout << "st1: " << st1 << endl;
            }
        }

        return -1;
    }


    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int len = nums1.size() + nums2.size();
        if(len % 2 == 1) {
            return getKthElement(nums1, nums2, len / 2 + 1);
        }
        return static_cast<double>(getKthElement(nums1, nums2, len / 2 + 1) + getKthElement(nums1, nums2, len / 2)) / 2;

    }
};