为何未返回start和end变量的Binary Search函数仍能正常工作？

原代码 #

function searchTarget(N, A, X) {
    let start = 0;`=
    let end = A.length - 1;
    // = mid  , < mid , > mid (3 sections)
    // so the target element which needs to be searched lies among these 3 sections
    while (start <= end) {
    let mid = Math.floor((start + end) / 2);
        if (X === A[mid]) {
            return mid;
        }
        else if (X < A[mid]) {
            end = mid - 1;
        }
        else {
            start = mid + 1;
        }
        
    }
    return -1;
}

console.log(searchTarget(N, A, X));

用户疑问 #

我存在一个疑问：在上述Binary Search（二分查找）函数中，我们并未返回start和end变量，这个函数是如何实现查找功能的？

解答 #

这个函数的核心逻辑根本不需要返回start和end，它的查找流程是这样的：

• 首先初始化start和end来框定当前要搜索的数组范围
• 每次循环计算中间位置mid，直接拿目标值X和A[mid]对比：
  1. 如果相等，直接返回mid——这就是找到目标的位置，任务完成
  2. 如果X比A[mid]小，说明目标在左半段，把end改成mid-1，缩小搜索范围到左边
  3. 如果X比A[mid]大，说明目标在右半段，把start改成mid+1，缩小搜索范围到右边
• 循环一直重复，直到找到目标返回位置，或者start超过end（说明整个数组搜完都没找到），就返回-1

说白了，start和end只是用来不断缩小搜索范围的“边界标记”，它们的作用是帮我们每次只搜一半的元素，不用遍历整个数组。真正的返回值要么是找到的位置mid，要么是表示没找到的-1，完全不需要把边界变量返回出去。

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