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

Falldawn 发表于 2024-5-3 15:47
你可以说是偷懒，简单一句话总结，就是如果初始化为0和n - 1并且mid右偏的前题条件是这个解一定在[0, n) ...

解不存在的话，确定要像一楼那样，直接把-1或者n返回去吗？解不存在的例子都贴了个LC34出来了。

SoWhat0309 发表于 2024-5-3 12:41
同样楼上的道理，很多时候初始化加上一个n配合left < right是可能收敛到n的，但这不表示最后解是n而是表 ...

我也是好好在讨论，你还是没回答为什么初始化为left = 0, right = n

我已经说了原因，因为mid左偏，所以mid右偏的时候left = -1, right = n - 1，这是一样的道理啊

解是有可能不在搜索空间的

Falldawn 发表于 2024-5-3 15:51
我也是好好在讨论，你还是没回答为什么初始化为left = 0, right = n

我已经说了原因，因为mid左偏，所 ...

初始化右边界是n？我也没说过这个，贴出来的一个题目右边界是n是因为最大解真的能取到n。

所以类似在'[1,2,3,4,5]里搜x == 6最小index、解不存在的话，直接像一楼那样直接返回n完全不判断么？

补充内容 (2024-05-04 06:01 +08:00):

再把LC34的代码贴出来。请问之前说的，不按照一楼那样取边界就一定是错的，依据在哪里？

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int n = nums.length;
        int[] res = {-1, -1};
        // rightmost equal index
        int l = 0, r = n-1;
        while (l < r) {
            int mid = l + (r - l + 1)/2;
            if (nums[mid] > target) {
                r = mid - 1;
            } else {
                l = mid;
            }
        }
        if ( l < nums.length && nums[l]==target ){
            res[1] = l;
        }
        // leftmost equal index
        l = 0; r = n-1;
        while (l < r) {
            int mid = l + (r - l)/2;
            if (nums[mid] >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        if (l < nums.length && nums[l] == target) {
            res[0] = l;
        }
        return res;
    }
}

补充内容 (2024-05-04 06:13 +08:00):

你的观点一直都是，不按照你的取边界方法，就全是错的。如果不按照一楼那个绕了一个弯的做法做，“为什么初始化为left = 0, right = n”这个问题意义在哪里。

一共不到10行的算法，作为模板还要临时检查调整4-5行，我觉得我是记不下来的。这也不能称之为模板了吧

djmiss 发表于 2024-5-3 13:16
如果一个模板还要临时检查那么多东西，我觉得我是记不下来的。

不是记啊，是理解，理解了就不需要记。

SoWhat0309 发表于 2024-5-3 13:01
初始化右边界是n？我也没说过这个，贴出来的一个题目右边界是n是因为最大解真的能取到n。

所以类似在' ...

对不起！那我改一下说法，按照上面总结的这么写，不会错。

其实争论的焦点在哪里？就是在解的范围

while (left < right)这个最后收敛在left = right这点上，如果left和right取的值覆盖了解的范围，那就没问题，因为最终收敛的那个解一定在left = right，而且不需要再check了。

我上面总结的是任何情况下都可以，也就是把解的范围都覆盖了。

当然可以不按照上面写。

How about leetcode 162? I feel we can't use your template.

nihonhumita 发表于 2024-5-7 19:57
How about leetcode 162? I feel we can't use your template.

完全可以啊，只是这里不能初始化为right = n，原因是A[mid] 和A[mid + 1] 比较，初始化为right = n会导致mid + 1可能越界

所以初始化为left = 0, right = n - 1就对，因为解就在[0, n)

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

复制代码

SoWhat0309 发表于 2024-5-3 13:01
初始化右边界是n？我也没说过这个，贴出来的一个题目右边界是n是因为最大解真的能取到n。

所以类似在' ...

感谢你的一直讨论，今天网友回复然后发现一个初始化为right = n是错的例子。所以最好还是left 和right初始化的值覆盖解的范围是对的。解可能为-1或n才初始化为left = -1或right = n

LC 162

这里不能初始化为right = n，原因是A[mid] 和A[mid + 1] 比较，初始化为right = n会导致mid + 1可能越界。所以初始化为left = 0, right = n - 1就对，因为解就在[0, n)

Falldawn 发表于 2024-5-7 21:28
完全可以啊，只是这里不能初始化为right = n，原因是A[mid] 和A[mid + 1] 比较，初始化为right = n会导致mi ...

Thanks. How about leetcode 1539? I found I need to change your template below to work
1) l < r  =>  l <= r
2) r = m  =>  r = m - 1

1. int findKthPositive(vector<int>& arr, int k) {
   
2.         int l = 0;
   
3.         int r = arr.size() - 1;
   
4. 
   
5.         while (l <= r) {
   
6.             int m = (l + r) / 2;
   
7.             if (arr[m] - (m + 1) < k) {
   
8.                 l = m + 1;
   
9.             }
   
10.             else
    
11.                 r = m - 1;
    
12.             }
    
13.         }
    
14.         return k + r + 1;
    
15. }

复制代码