在偶数长度数组上用 left + (right - left) / 2 returns 小数点 (.5) 计算中点。那有什么好处？

Question

所以我一定是误解了一些基本的东西，但我环顾四周，找不到答案。

我在这里查看了一个关于在二进制搜索期间计算数组中点的线程 -

Calculating mid in binary search 但它没有帮助。

我的问题是我见过的许多算法都使用了这个：midpoint = left + ((right - left) / 2).

过去我用过很多次，但现在我有些不明白。

下面是我要执行的代码 - 第一个 console.log 中点日志 6.5.

我不会在索引 arr[6.5] 找到任何东西。

我的代码有问题吗，

还是我没听懂？

let arr = ['w','x','y','z','a','b','d','e','f','g','h','i','j','k']

function rotationPoint(arr){

  let ceiling = arr.length -1
  let floor = 0
  
  while(floor < ceiling){
    
    let midpoint = floor + ((ceiling - floor) / 2)
    console.log(midpoint)

    if(arr[floor] > arr[midpoint]){
      //we know the value is in the first half
      ceiling = midpoint
    }else{
      floor = midpoint
    }
    
        if(arr[floor + 1] === arr[ceiling]){
      return ceiling
    }
  }
  

  }
  

}

console.log(rotationPoint(arr))

Answer 1

您看到的算法可能使用 left 和 right 作为整数类型（int、long 等）。对于整数类型，7 / 2 是 3（3.5 小数部分被截断）。 JavaScript 的数字是浮点数，不是整数，所以你在那种情况下使用 Math.floor (or in modern environments, Math.trunc¹)：

midpoint = Math.floor(left + ((right - left) / 2));

这样，你得到一个整数。

如果这是针对数组中的索引，您可以改用移位。

（您也可以使用 Math.round，它会取整而不是取整，但大多数这些算法都是根据积分数学重新定义的...）

¹ floor 和 trunc 之间的区别在于 floor 总是在数字上舍入，这意味着 Math.floor(-0.5) 是 -1。 trunc 只是去掉小数部分，所以 Math.trunc(-0.5) 是 0（好吧，从技术上讲是 -0，但那是另一个话题了...）。

Answer 2

您可以将左右相加并除以二得到中点。

Javascript中的数组索引与按位运算具有相同的范围。要除以二并获得整数值，您可以添加一些位移。

midpoint = (floor + ceiling) >> 1;

Answer 3

您示例中的代码是运行长度为 14 的数组，但您的问题询问的是奇数长度数组。如果您实际上使用奇数长度数组，您的代码应该没问题。对于偶数长度的数组，您确实会得到一个十进制索引，因此您需要通过舍入或截断来选择结果的一侧或另一侧。

在偶数长度数组上用 left + (right - left) / 2 returns 小数点 (.5) 计算中点。那有什么好处？

Calculating a midpoint with left + (right - left) / 2 returns a decimal (.5) on even length arrays. What good is that?

javascript

algorithm

binary-search