Java二分查找基础的两个技术疑问（DSA入门）

首先附上你提供的二分查找实现代码：

public class sample{
    public static void main(String[] args) {
        int[] nums = {2, 2, 4, 6, 8, 12, 14, 15};
        int target = 12;
        int ans = search(nums, target);
        System.out.println(ans);
    }
    static int search(int[] arr, int target){
        int start = 0;
        int end = arr.length - 1;
        while(start <= end){
            int mid = start + (end-start)/2;
            if (target < arr[mid]){
                end = mid -1;
            }
            else if (target > arr[mid]){
                start = mid +1;
            }
            else{
                return mid;
            }
        }
        return -1;
    }
}

问题1：为何在if和else if分支中不使用return语句？当找到目标值后，方法如何返回结果？ #

if和else if分支的作用是缩小查找区间：当目标值比中间元素小，就把查找范围调整到左半部分（end = mid -1）；当目标值比中间元素大，就调整到右半部分（start = mid +1）。这时候还没找到目标值，自然不需要返回。

只有当进入else分支时，说明target == arr[mid]，也就是找到了目标元素的索引位置，此时直接通过return mid返回结果。如果整个循环执行完毕都没进入else分支，说明数组中不存在目标值，最后通过return -1表示查找失败。

问题2：请解释代码中int mid = start + (end - start)/2的数学原理及设计原因 #

数学原理 #

这个式子和(start + end) / 2完全等价，展开推导就能看出来：

start + (end - start)/2 = (2*start + end - start)/2 = (start + end)/2

本质都是计算start和end两个索引的中间值，用来定位当前查找区间的中间元素。

设计原因 #

核心是避免整数溢出：Java的int类型有固定取值范围（-2^31 到 2^31-1）。如果start和end都是接近Integer.MAX_VALUE的大数值，直接计算start + end会超出int的最大值，导致溢出变成负数，进而得到错误的mid值。

而end - start的结果一定是非负的（因为循环条件保证start <= end），不会触发溢出，再加上start后，结果始终在int的合法范围内，能保证mid的计算准确。

内容的提问来源于stack exchange，提问作者maulik