He notado que las personas usan diferentes formas de calcular el punto medio de una matriz ordenada y sus sub-matrices. Esto se usa a menudo en la búsqueda binaria.
El primer método parece un poco mejor ya que es más simple. ¿La segunda forma ofrece alguna ventaja?
const mid = Math.round((left + right) / 2);y
const mid = left + Math.round((right - left) / 2);y (por respuesta)
const mid = ( left + right ) >>> 1;En primer lugar, no creo que Math.round sea lo que encontrará más a menudo, porque redondeará hacia arriba cualquier número entero + 0,5. Por ejemplo, Math.round(3.5) === 4 . Esta no es la forma más común de encontrar el punto medio entero. La razón principal es que las formas alternativas que involucran números enteros (a diferencia de los números de punto flotante), todos redondeados hacia abajo:
(left + right) >>> 1 ( >>> es el desplazamiento a la derecha sin firmar)~~((left + right) * 0.5) ( ~~ es una forma de convertir a entero)left + right Estas formas que involucran números enteros son probablemente más rápidas que llamar a Math.round() , verifíquelo en su navegador. Además, JavaScript es una excepción entre los lenguajes, ya que no diferencia, excepto dentro de las operaciones, entre enteros y flotantes. La mayoría de los idiomas usarán explícitamente números enteros para índices de matriz, por lo que el desplazamiento a la derecha de arriba es obviamente para ellos la forma más rápida de dividir por 2. Esto también ha influido en la literatura, por lo que encontrará ⌊(left+right)/2⌋ mucho más a menudo que ⌈(left+right)/2⌉ . Si insiste en usar la biblioteca Math , esto significa usar Math.floor((left + right) / 2) .
La única razón para no usar operaciones con enteros podría ser que los enteros son enteros de 32 bits firmados en JavaScript, mientras que los flotantes son flotantes IEEE 754 de 64 bits, que tienen 53 bits significativos (incluido un bit implícito 1 ). Si los índices de su matriz pueden exceder 2147483637 (2 31 -1), no puede usar operaciones con números enteros. Sin embargo, esta situación es poco probable, también porque el tamaño de las matrices de JavaScript no puede exceder 4294967296 (2 32 ) de todos modos.
En cuanto a su pregunta, la segunda forma no solo es un poco más larga en la pantalla, sino que también implica una operación matemática más. La segunda forma tendría una ventaja sobre la primera si los índices pudieran acercarse a Number.MAX_SAFE_INTEGER , que es 9007199254740991 (2 53 -1) (porque la resta permitiría que los índices estuvieran más cerca de ese límite), pero como hemos visto esto no es posible para las matrices de JavaScript.