二分查找中关于mid定边界问题的解析（查找数组中小于等于特定值的元素的最大下标/大于等于特定值的元素的最小下标问题）

秒速五厘米 2023-09-28 23:17 38阅读 0赞

> **有时候写二分查找，我们会看见有的写 mid = (l + r) / 2，而有时候见到有人写 mid = (l + r +1) / 2，所以我有时候会心生疑问：我们究竟应该怎么写？这有什么规律吗？**

首先看下面两段代码：

查找数组中小于等于特定值的元素的最大下标：

public static int binarySearchUpper(int[] nums, int target){
        
            //寻找数组中小于等于target的元素最大下标,数组升序排列
            int l = 0;
            int r = nums.length - 1;
            while(l < r){
        
                int mid = (l + r + 1) / 2;
                if(nums[mid] <= target){
        
                    l = mid;
                }
                else{
        
                    r = mid - 1;
                }
            }
            if(nums[l] > target){
        
                return -1;
            }
            return l; 
        }

查找数组中大于等于特定值的元素的最小下标:

public static int binarySearchLower(int[] nums, int target){
        
            //寻找数组中大于等于target的元素最小下标,数组升序排列
            int l = 0;
            int r = nums.length - 1;
            while(l < r){
        
                int mid = (l + r) / 2;
                if(nums[mid] >= target){
        
                    r = mid;
                }
                else{
        
                    l = mid + 1;
                }
            }
            if(nums[l] < target){
        
                return -1;
            }
            return l; 
        }

**解释：**  
首先我们要知道：(l + r) / 2 是m向下取整，(l + r + 1) / 2 是m向上取整。观察上面两段代码，我们可以发现，在查找边界的问题上，l有两种变化：l = mid 和 l = mid + 1，同时，r也有两种变化： r = mid 和 r = mid - 1，而**mid = (l + r) / 2 中，mid的计算结果可能等于l，但是绝对不会等于r（l != r），所以，当mid的计算结果等于l，而边界变化又是l = mid时，那么程序就会陷入死循环，** 这样说大家可能不好理解，我可以举一个例子，如：当 l = 4，r = 5时，mid = （4 + 5）/ 2 = 4，若此时边界变化为 l = mid，则下一次循环时，仍然是 l = 4，r = 5…所以这时我们一般使用m的向上取整 (l + r + 1) / 2 来规避这一问题，总的来说就是：**当边界变化出现 l = mid 时，我们应该选用 (l + r + 1) / 2 来规避程序陷入死循环！**