javascript - 二分查找提前退出？

Question

我正在尝试查找两个数组的重复项，并且其中一个数组明显更大，因此我在遍历较小的数组的同时对较大的数组进行二分搜索以查找该数字。但是，我的解决方案没有运行。

function bSearch(arr, num) {
  let start = 0
  let end = arr1.length - 1
  while (start <= end) {
    let middle = Math.round(start + end / 2)
    if (arr[middle] === num) {
      return arr[middle]
    } else if (arr[middle] < num) {
      start = middle
    } else {
      end = middle
    }
  }
  return false
}

function dup(arr1, arr2) {
  let output = []
  let shorterArray = arr1.length > arr2.length ? arr2 : arr1
  for (let i = 0; i < shorterArray.length; i++) {
    if (bSearch(arr1, shorterArray[i])) {
      output.push(shorterArray[i])
    }
  }
  return output
}

let arr1 = [1, 2, 3, 5, 6, 7], arr2 = [3, 6, 7, 8, 20]
dup(arr1, arr2)

// should return [3, 5, 7]
// currently only returns [3]

Answer 1

这里有一些小问题。

1. bSearch(arr1, ShortArray[i]) - 如果 arr1 很短，则仅搜索它。

2. 在二分搜索中，您使用 arr1 的长度，而不是 arr 来进行初始 end 变量声明。

3. let middle = Math.round(start + end/2) - .round() 以不同方式进行舍入，请使用 .floor() .

4. Math.round((start + end)/2 - start 和 end 加法应放在括号内

5. 二进制逻辑应该增加或减少中间，否则你最终会陷入无限循环，即 (6 + 6)/2 === 6

因此:

if (arr[middle] === num) {
    return arr[middle]
} else if (arr[middle] < num) {
    start = middle + 1
} else {
    end = middle - 1
}

JsBin:https://jsbin.com/ciyusodisi/edit?js,console