二分查找死循环问题

梦里梦外; 2022-10-20 00:58 204阅读 0赞

# 二分查找死循环问题 #

看代码

public class Solution_69 { 
    
        public int mySqrt(int x) { 
            // 特殊值判断
            if (x == 0) { 
                return 0;
            }
            if (x == 1) { 
                return 1;
            }
    
            int left = 1;
            int right = x / 2;
            // 在区间 [left..right] 查找目标元素
            while (left < right) { 
                // 取中间数 mid 下取整时
                int mid = left + (right - left ) / 2;
    
                // 调试语句开始
                try { 
                    Thread.sleep(1000);
                } catch (InterruptedException e) { 
                    e.printStackTrace();
                }
                System.out.println("left = " + left + 
                ", right = " + right + ", mid = " + mid);
                // 调试语句结束
    
                // 注意：这里为了避免乘法溢出，改用除法
                if (mid > x / mid) { 
                    // 下一轮搜索区间是 [left..mid - 1]
                    right = mid - 1;
                } else { 
                    // 下一轮搜索区间是 [mid..right]
                    left = mid;
                }
            }
            return left;
        }
    
        public static void main(String[] args) { 
        	Solution_69 solution = new Solution_69();
            int x = 9;
            int res = solution.mySqrt(x);
            System.out.println(res);
        }
    }

输出

left = 1, right = 4, mid = 2
    left = 2, right = 4, mid = 3
    left = 3, right = 4, mid = 3
    left = 3, right = 4, mid = 3
    left = 3, right = 4, mid = 3
    left = 3, right = 4, mid = 3

这时出现了死循环，我们只要把计算`mid`的代码改成`int mid = left + (right - left ) / 2+1;`向上取整就可以了。  
输出

left = 1, right = 4, mid = 3
    left = 3, right = 4, mid = 4
    3

**问**：为什么有些时候取 mid 的时候需要上取整？  
**回答**：是否需要上取整，只和区间划分的逻辑有关。如果不调整，会出现死循环。

**结论**：当区间只剩下两个元素的时候，`left = mid` 和 `right = mid - 1` 这种划分方式，如果 `mid` 使用默认下取整的方式，在数值上 `left = mid`，而它对应的其中一个区间是 `[mid..right]`，在这种情况下，下一轮搜索区间还是 `[left..right]`，搜索区间没有减少，会进入死循环。

**提示**：「**看到边界设置的代码是 `left = mid` 时，需要把 `mid` 的取法调整为上取整，以避免死循环**」，这件事情也完全不用记忆，题目做得多了，自然而然就记住了。还是我们在题解中和大家多次强调的一件事情：**遇到代码出错的时候，一定要耐心调试，把变量打印出来看一下，是最好的学习的方法**。

# 参考 #

[写对二分查找不能靠模板，需要理解加练习][Link 1]

[Link 1]: https://leetcode-cn.com/problems/search-insert-position/solution/te-bie-hao-yong-de-er-fen-cha-fa-fa-mo-ban-python-/