行业协会网站模板wordpress 模板 淘宝客模板 wordpress 主题

二分查找向下取整导致的死循环

        考虑伪题目：从数组arr中查找出目标元素target对应的下标，如果数组中不存在目标元素，找

到第一个元素值小于target的元素的下标。

        编写二分查找算法如下：

    @Testvoid testBinarySearch(){int[] arr = new int[]{1, 2};int left = 0, right = arr.length - 1, target = 2;while(left < right){int mid = left + (right - left) / 2;if(arr[mid] == target){System.out.println("Find target index is :" + mid);}else if(arr[mid] > target){right = mid + 1;}else if(arr[mid] < target){left = mid;}System.out.println("Program is running...");}}

        通过代码执行结果可以得出此二分查找陷入死循环：

        分析以上二分查找代码逻辑，题目意思可以理解为寻找第一个小于或者等于target目标元素的下标。当只有两个元素的时候，此时情况[left, right]由于Java是向下取值，此时right和left仅仅相隔一个元素，计算mid相当于（left + left + 1）/ 2等于left，mid对应left位置，由于arr[mid] < target，所以left取值为mid，也就是[left，right]的相对位置保持不变，所以陷入死循环。

        解决方案，将向下取整变为向上取整，完美解决，修改后代码如下：

在二分查找中【只有两个元素时】出现死循环，如下：

[left，right]==>取值策略：left = mid，right = mid - 1，此时只有进入right循环时才会改变left、right的相对位置，否则进入left = mid死循环。

解决方案：将mid计算方案中向下取整改为向上取值，此时只有两个元素的时候永远计算的是较大者。【要针对具体情况讨论】

 69. x 的平方根 

        题目链接：69. x 的平方根 - 力扣（LeetCode）

        上面的问题的引入以及解答均是自己在做lc题目69的时候看到的题解中某句话的理解。

 参考链接

69. x 的平方根 - 力扣（LeetCode）https://leetcode.cn/problems/sqrtx/solutions/7866/er-fen-cha-zhao-niu-dun-fa-python-dai-ma-by-liweiw/?envType=study-plan-v2&envId=top-interview-150