再谈Binary Search 模板while (left < right)的理解

nihonhumita 发表于 2024-5-7 22:50
Thanks. How about leetcode 1539? I found I need to change your template below to work
1) l < r  = ...

1539是比较简单的题目了，难一点的1060，你可以看一下Understanding of Binary Search Template，这里我把题目全部列出来了

LC 1539
这里r 也必须初始化为 n，因为解可能在n

1. public int findKthPositive(int[] A, int k) {
   
2.         if (A == null || A.length == 0 || k <= 0) {
   
3.             return -1;
   
4.         }
   
5.         
   
6.         int l = 0, r = A.length, m;
   
7.         while (l < r) {
   
8.             m = (l + r) / 2;
   
9.             if (A[m] - 1 - m < k) {
   
10.                 l = m + 1;
    
11.             } else {
    
12.                 r = m;
    
13.             }
    
14.         }
    
15.         return l + k;
    
16.     }

复制代码

LC 1060
Input: nums = [4,7,9,10], k = 3.
We can find the first index where the missing elements >= k. Here we can find index = 2 is the min index where we have missing elements = A[2] - A[0] - (2 - 0) = 3 >= k = 3, then the kth missing number is after A[1] = 7.

Find left bound where A[mid] - A[0] - mid >= k, right must be initialized to n here because the result can lie outside [0, n).
For ex, A[2] - A[0] - (2 - 0) = 1 < k = 3.
Input: nums = [1,2,4], k = 3
Output: 6

1. public int missingElement(int[] A, int k) {
   
2.         int left = 0, right = A.length;
   
3.         while (left < right) {
   
4.             int mid = left + (right - left) / 2;
   
5.             if (A[mid] - A[0] - mid < k) {
   
6.                 left = mid + 1;
   
7.             } else {
   
8.                 right = mid;
   
9.             }
   
10.         }
    
11.         return A[0] + k + left - 1;
    
12.     }

复制代码

Input: nums = [4,7,9,10], k = 3.
We can also find the last index where the missing elements < k. Here we can find index = 1 is the max index where we have missing elements = A[1] - A[0] - 1 - 0 = 2 < k = 3, then the kth missing number is after A[1] = 7.
Find right bound where A[mid] - A[0] - mid < k

1. public int missingElement(int[] A, int k) {
   
2.         int left = 0, right = A.length - 1;
   
3.         while (left < right) {
   
4.             int mid = right - (right - left) / 2;
   
5.             if (A[mid] - A[0] - mid < k) {
   
6.                 left = mid;
   
7.             } else {
   
8.                 right = mid - 1;
   
9.             }
   
10.         }
    
11.         return A[0] + k + left;
    
12.     }

复制代码

Because finally we need to locate a subarray of two elements where l = r - 1, and the solution will be in this range (A[l], A[r]), which is A[l] + updated k.

1. public int missingElement(int[] A, int k) {
   
2.         int left = 0, right = A.length - 1;
   
3.         int missing = A[right] - A[left] - (right - left);
   
4.       
   
5.         if (k > missing) {
   
6.             return A[right] + k - missing;
   
7.         }
   
8.       
   
9.         while (left < right - 1) {
   
10.             int mid = left + (right - left) / 2;
    
11.             missing = A[mid] - A[left] - (mid - left);            
    
12.             if (missing < k) {
    
13.                 k -= missing;
    
14.                 left = mid;
    
15.             }
    
16.             else {
    
17.                 right = mid;
    
18.             }
    
19.         }
    
20.       
    
21.         return A[left] + k;
    
22.     }

复制代码

个人经验，写的时候按照stl的lowerbound和upperbound的api设计基本就可以解决几乎所有问题，然后再想办法把lowerbound和upperbound写出来

wsha8 发表于 2024-6-21 23:24
个人经验，写的时候按照stl的lowerbound和upperbound的api设计基本就可以解决几乎所有问题，然后再想办法把 ...

STL？你说的C++嘛？

一开始我写得有点问题，左右边界只要包涵所有可能解即可

Falldawn 发表于 2024-06-22 10:17:42
STL？你说的C++嘛？

一开始我写得有点问题，左右边界只要包涵所有可能解即可

对，stl有两个二分查找的函数，lower_bound和upper_bound，这两个api设计的是最好也是最标准的

OnjoujiToki 发表于 2024-5-3 23:19
比起左右端点这种几何意义上的理解，可以尝试从true/false来进行二分，左闭右开
while loop就可以变成
wh ...

有点没看懂 abs(t-f) 是什么意思，可以再解释一下么

有人有兴趣一起刷题吗朋友?   我在找刷题抱团搭子。