关于二分查找基础知识的一些疑问

Question

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;
    }
}

我知道这可能很蹩脚，但我才刚刚开始使用 java 和 dsa。 疑问#1 -> 为什么我们不在 if、else if 中使用 return 语句？一旦找到数字，该方法如何给出该值？ 疑问#2 -> 请解释 int mid = start + (end+start)/2 背后的数学原理和原因；

Answer 1

我们不在 if / else if 中使用 return 语句，因为 while 循环必须继续缩短数组。如果我们添加一个 return 语句，就会破坏 while 循环。

该方法不返回找到的值，而是返回该值在数组中存储的索引。

关于疑问2：原因是我们想缩短数组，这样我们就不会在某个值之后或之前查找。二分搜索算法的工作原理是在每次迭代时将数组减半。因此，如果您正在查找数字 10 的索引，并且您检查的当前数字是 6，则没有理由查看之前的数字（这就是为什么二分搜索仅适用于排序数组），因此使用 if / else 中的语句如果我们设置边界（顶部或底部边界）。

Answer 2

在

if

和

else if

中，您仍在尝试查找目标元素。如果目标元素小于您当前正在查看的数组元素，则输入

if

子句。如果目标元素大于您当前正在查看的数组元素，则执行

else if

。在这些情况下，您还没有找到目标元素，因此您不想返回任何内容。如果当前元素等于目标元素，则执行

else

部分，因此您找到了要查找的内容并返回找到目标的索引。

代码

int mid = start + (end - start) / 2;

以有助于避免整数溢出问题的方式计算中间索引

mid

：

start

是搜索范围当前最左边的索引。

end

是搜索范围当前最右边的索引

公式

(end - start) / 2

计算起始索引和结束索引之间的距离，然后将其除以2以获得中间点。在此结果中添加 start 即可得到实际的中间索引。

使用

(end - start)

而不是

(end + start)

的原因是为了防止整数溢出。如果您使用 (end + start) 并且

start

和

end

是很大的值，则将它们相加可能会导致整数溢出问题。减去它们可以让您计算中间点而不会出现这个问题。