二进制搜索逻辑

Question

我试图做一个二进制搜索算法，但我遇到了一个逻辑问题，我不明白为什么它不起作用...

var binarySearch = function(list, num) {
  var low = 0, high = list.length - 1, mid = Math.floor((high - low) / 2);
  while(mid != num) {
    if(num > list[mid]) {
      low = mid;
      mid = Math.floor((high - low) / 2);
    } else {
      high = mid;
      mid = Math.floor((high - low) / 2);
    }
  }
  return mid;
}

var arr = [1, 3, 4, 5, 8, 10, 43, 55]
binarySearch(arr, 3);

这段代码 returning 3 没问题，但如果我输入 43 这样的数字，它就不会 return 任何东西...

Answer 1

这是JavaScript中二分查找的简单实现：

function binarySearch(arr, x, start, end) {
  if (start > end) {
    return false;
  }
  let mid = Math.floor((start + end) / 2);
  if (arr[mid] == x) {
    return true;
  } else if (arr[mid] > x) {
    return binarySearch(arr, x, start, mid - 1);
  } else {
    return binarySearch(arr, x, mid + 1, end);
  }
}
let arr = [1, 3, 4, 5, 8, 10, 43, 55]
let x = 43;
if (binarySearch(arr, x, 0, arr.length - 1)) {
  console.log(x + ' found');
} else {
  console.log(x + ' NOT found');
}

Answer 2

您的主要问题是：

您在 while 循环中的条件。 mid 是数组中的索引，而不是元素。您可以使用 list[mid] 获取中点的元素。
您正在将 low 和 hight 设置为 mid。但是您不需要重新检查这些（您是否已经在检查 while 循环中的 mid 位置）。您可以改用 mid+1 或 mid-1。
您重新计算的中点不正确。您想使用 Math.floor((high + low) / 2); 获得最高价和最低价之间的平均值（注意 +）。
目前，您的 while 循环只有在找到匹配项后才会停止。一旦用尽所有可能性，您还需要停止它。这可以使用额外的检查来完成，以检查低指针是否没有超过高指针。
如果找不到该元素，则需要 return 一个 -1。这可以通过检查您的 low 和 high 指针来完成。

var binarySearch = function(list, num) {
  var low = 0, high = list.length - 1, mid = Math.floor((high + low) / 2);
  while(list[mid] != num && low <= high) {
    if(num > list[mid]) {
      low = mid+1;
      mid = Math.floor((high + low) / 2);
    } else {
      high = mid-1;
      mid = Math.floor((high + low) / 2);
    }
  }
  
  return low <= mid ? mid : -1;
}

var arr = [1, 3, 4, 5, 8, 10, 43, 55]
console.log(binarySearch(arr, 55));

您可以通过在 while 循环中执行相等性检查并移动 mid:

的计算来稍微简化您的代码

var binarySearch = function(list, num) {
  var low = 0, high = list.length - 1;
  while(low <= high) {
    var mid = Math.floor((high + low) / 2);
    if(list[mid] === num)
      return mid;
      
    if(num > list[mid])
      low = mid+1;
    else
      high = mid-1;
  }
  
  return -1;
}

var arr = [1, 3, 4, 5, 8, 10, 43, 55]
console.log(binarySearch(arr, 55));

二进制搜索逻辑

Binary Search Logic

javascript

binary-search

node.js

binary-search-tree