Binary Search二分查找代码陷入while无限循环 求助排查原因

问题根因 #

mid的计算语句放在了while循环外部，只会在进入循环前计算一次。后续每次循环修改start、end边界后，mid值不会同步更新，判断逻辑一直基于初始的mid值执行，就会陷入无限循环。

修复方案 #

把mid = start + (end - start)/2;这行代码移动到while循环内部的第一行即可。

修复后完整代码 #

public class BinarySearch {
    public static int doBinarySearch(int[] arr, int target){
        int start = 0;
        int end = arr.length - 1;
        while(start <= end){
            // 每次循环重新计算当前边界下的mid值
            int mid = start + (end - start)/2;
            if(target == arr[mid])
            {
                return mid;
            }
            else if(target < arr[mid])
            {
                end = mid - 1;
            }
            else if(target > arr[mid])
            {
                start = mid + 1;
            }
        }
        return -1;
    }


    public static void main(String[] args){
        int[] array = {2,3,4,5,6,7,8,9};
        int target = 3;
        int answer = doBinarySearch(array, target);
        System.out.println(answer);
    }
}

额外注意事项 #

• 调用该二分查找方法前，要保证传入的数组是升序有序的，否则查找逻辑不生效
• 你当前用start + (end - start)/2计算mid的写法是正确的，可以避免(start+end)计算结果超出int取值范围的溢出问题

内容的提问来源于stack exchange，提问作者Mera Bharat Mahaan