binary-search - 如果找不到搜索值，二分查找如何工作？

Question

如果找不到搜索值，二分查找如何工作？

例如，如果您要在此数组中搜索 60:

ANDMarks = {1, 6, 38, 39, 45, 55, 57, 61, 72, 73, 88, 96}

结局如何？我试运行了代码，直到搜索到索引 6 和 7。为了更容易得到我要问的内容，这是我的试运行:

步骤:

1.找到中间值。

Middle value = (index of 1st element + index of last element)/2
Middle value = (0+11)/2
Middle value = 5 
Middle value = element in 5th index => 55

Indexes     0   1   2   3   4   **5**   6   7   8   9   10  11
Elements    1   6   38  39  45  **55**  57  61  72  73  88  96

第 2 步。中间值 (55) != 60

步骤 3. 中间值 < 搜索值 (55 < 60)

考虑数组中位于中间值之后的部分

Indexes     6   7   8   9   10  11
Elements    57  61  72  73  88  96

第 4 步。

Middle value = (index of 1st element + index of last element)/2
Middle value = (6+11)/2
Middle value = 8
Middle value = element in 8th index => 72

Indexes     6   7   **8**   9   10  11
Elements    57  61  **72**  73  88  96

第 5 步。中间值 (72) != 60

第 6 步. 中间值 > 搜索值 (72 > 60)

考虑数组中位于中间值之前的部分。

Indexes     6   7
Elements    57  61

现在发生了什么？

Answer 1

我知道我来晚了，您现在可能已经弄明白了，但是尽管如此，这个问题有超过 5000 次浏览，但没有明确的解释。

也许我的解释可以帮助任何有抱负的计算机科学爱好者。

Here is my explanation目前，我在堆栈溢出方面没有足够的声誉，所以它不允许我嵌入图像。请随时检查解释，因为它包含图像。

如果有人喜欢或同意，请随时竖起大拇指，因为这会鼓励我在 Stack Overflow 上留下更多回复和帖子。

下面是我的 JavaScript 代码，你可以在 Chrome 开发者工具中复制粘贴，调试它，看看它是如何工作的。

function binarySearch(arr, val) {
  let mid = Math.floor(arr.length / 2);
  let left = 0;
  let right = arr.length - 1;
  while (arr[mid] !== val && ((left != mid) && (mid != right))) {
    if (val > arr[mid]) {
      left = mid + 1;
      mid = Math.floor((left + right) / 2);
    } else if (val < arr[mid]) {
      right = mid - 1;
      mid = Math.floor((left + right) / 2);
    }
  }
  return arr[mid] === val ? mid : -1;
}

arr1 = [3, 7, 9, 11, 12, 14, 20]
console.log(binarySearch(arr1, 14));
console.log(binarySearch(arr1, 1));
console.log(binarySearch(arr1, 23));
console.log(binarySearch(arr1, 8));
console.log(binarySearch(arr1, 16));

编码愉快!