Javascript 中的二分查找

IT技术 javascript binary-search

2021-01-22 14:50:37

我正在尝试在 JavaScript 中实现二进制搜索算法。事情似乎没问题，但我的 return 语句似乎返回 undefined？任何人都可以告诉这里有什么问题吗？

谢谢。

var a = [
    1,
    2,
    4,
    6,
    1,
    100,
    0,
    10000,
    3
];

a.sort(function (a, b) {
    return a - b;
});

console.log('a,', a);

function binarySearch(arr, i) {
    var mid = Math.floor(arr.length / 2);
    console.log(arr[mid], i);

    if (arr[mid] === i) {
        console.log('match', arr[mid], i);
        return arr[mid];
    } else if (arr[mid] < i && arr.length > 1) {
        console.log('mid lower', arr[mid], i);
        binarySearch(arr.splice(mid, Number.MAX_VALUE), i);
    } else if (arr[mid] > i && arr.length > 1) {
        console.log('mid higher', arr[mid], i);
        binarySearch(arr.splice(0, mid), i);
    } else {
        console.log('not here', i);
        return -1;
    }

}
var result = binarySearch(a, 100);
console.log(result);

6个回答

以这种方式编写搜索函数很有用，如果未找到该元素，它会返回一个负值，指示新元素的插入点。此外，在二分查找中使用递归是多余且不必要的。最后，通过提供比较器函数作为参数来使搜索算法通用是一个很好的做法。下面是实现。

function binarySearch(ar, el, compare_fn) {
    var m = 0;
    var n = ar.length - 1;
    while (m <= n) {
        var k = (n + m) >> 1;
        var cmp = compare_fn(el, ar[k]);
        if (cmp > 0) {
            m = k + 1;
        } else if(cmp < 0) {
            n = k - 1;
        } else {
            return k;
        }
    }
    return -m - 1;
}

此代码注释和单元测试在这里。

您的算法返回，-m -1但您在 jsfiddle 中的代码注释引用了-n -1. 可能有错别字？

2021-03-13 14:50:37

@Rafael 好奇你为什么喜欢>> 1？

2021-03-13 14:50:37

0 的返回值是不明确的。元素是在列表的头部，还是需要插入到那里？

2021-03-15 14:50:37

返回值 0 没有歧义，它明确表示“元素位于索引 0”。为了表示“元素应插入索引 0”，该函数将返回 -1（这是0的按位补码- “~x” == “-x-1”）。

2021-03-29 14:50:37

作为对怀疑者的回应，我将单元测试扩展为一组随机测试。一直以来，所有测试都通过。查看小提琴jsfiddle.net/pkfst550/48

2021-04-09 14:50:37

您没有明确返回递归内部调用（即return binarySearch()），因此调用堆栈展开而没有返回值。像这样更新你的代码：

// ...
if (arr[mid] === i) {
    console.log('match', arr[mid], i);
    return arr[mid];
} else if (arr[mid] < i && arr.length > 1) {
    console.log('mid lower', arr[mid], i);
    return binarySearch(arr.splice(mid, Number.MAX_VALUE), i);
} else if (arr[mid] > i && arr.length > 1) {
    console.log('mid higher', arr[mid], i);
    return binarySearch(arr.splice(0, mid), i);
} else {
// ...

看到一个工作小提琴

为什么要返回与目标匹配的值？这使得整个搜索变得多余！您应该返回索引。

2021-03-19 14:50:37

我建议编辑此答案以使用slice而不是splice. 人们不会期望搜索功能会改变大海捞针。我会用binarySearch(arr.slice(mid), i)andbinarySearch(arr.slice(0, mid), i)代替。

2021-03-21 14:50:37

@gb96，@MichaelBausano，我只是更新了 OP 的代码来解决他们指出的问题，返回值和splice不纯似乎与这个问题无关，所以我将它们保留原样以免弄乱答案

2021-03-26 14:50:37

太好了，谢谢。而且我猜，拼接原始数组可以吗？

2021-03-28 14:50:37

好吧，这取决于你。如果您想避免传递的数组发生突变，请事先克隆它（例如var _arr = arr.slice(0)）。这是一个小提琴。

2021-03-28 14:50:37

这个问题有很多可行的解决方案，但是一旦找到匹配项，所有解决方案都会提前返回。虽然这可能对性能有很小的积极影响，但由于二分搜索的对数性质，这可以忽略不计，如果比较函数的计算成本很高，实际上可能会损害性能。

更重要的是，它阻止了二进制搜索算法的一个非常有用的应用：查找匹配元素的范围，也称为查找下限或上限。

下面的实现返回一个索引0≤ i≤array.length使得给定的谓词是falseforarray[i - 1]和truefor array[i]。如果谓词false无处不在，array.length则返回。

/**
 * Return 0 <= i <= array.length such that !pred(array[i - 1]) && pred(array[i]).
 */
function binarySearch(array, pred) {
    let lo = -1, hi = array.length;
    while (1 + lo < hi) {
        const mi = lo + ((hi - lo) >> 1);
        if (pred(array[mi])) {
            hi = mi;
        } else {
            lo = mi;
        }
    }
    return hi;
}

为了论证起见，假设pred(array[-1]) === false和pred(array[array.length]) === true（当然，在这些点上永远不会评估谓词）。循环保持不变!pred(array[lo]) && pred(array[hi])。算法终止时1 + lo === hiwhich 意味着!pred(array[hi - 1]) && pred(array[hi])，所需的后置条件。

如果sort()相对于比较函数对数组进行ed compare，则该函数在调用时返回an的最小 插入位置item

binarySearch(array, j => 0 <= compare(item, j));

的插入位置是在其中，如果它在阵列中存在的物品会被发现的索引。

可以很容易地按如下方式按自然顺序实现数组的下限和上限。

/**
 * Return i such that array[i - 1] < item <= array[i].
 */
function lowerBound(array, item) {
    return binarySearch(array, j => item <= j);
}

/**
 * Return i such that array[i - 1] <= item < array[i].
 */
function upperBound(array, item) {
    return binarySearch(array, j => item < j);
}

当然，这在数组可以包含多个比较相同的元素时最有用，例如，元素包含不属于排序标准的附加数据。

虽然这并不能完全回答原始问题（尽管我对原始问题的意义感到困惑），但我还是投了赞成票，因为在 SO 上很难找到好的信息。一个建议，在生活允许的情况下，请为历史更长、活动更多的问题提供这样的答案。这样做将使更多人更容易获得您的知识和经验。:-)

2021-03-14 14:50:37

@Nolo 是的，这const是语义 - 虽然你的推理是错误的；）当然let会起作用，因为它更宽松，但这里严格const就足够了

2021-03-23 14:50:37

@Nolo 我不希望它在这个简单的情况下有所作为，编译器可以证明变量永远不会被重新分配。我仍然认为进入是一个好习惯;)

2021-04-05 14:50:37

lo + ((hi - lo) >> 1vs的优势是(hi + lo) >> 1什么？

2021-04-10 14:50:37

@dominic 发现得很好，很好的问题！(hi + lo)只要元素多于整数类型范围的一半，就会溢出。这是这些类型计算中的一个众所周知的问题，例如参见ai.googleblog.com/2006/06/...

2021-04-10 14:50:37

二分搜索 (ES6)

自下而上：

function binarySearch(arr, val) {
  let start = 0;
  let end = arr.length - 1;

  while (start <= end) {
    let mid = Math.floor((start + end) / 2);

    if (arr[mid] === val) {
      return mid;
    }

    if (val < arr[mid]) {
      end = mid - 1;
    } else {
      start = mid + 1;
    }
  }
  return -1;
}

递归：

function binarySearch(arr, val, start = 0, end = arr.length - 1) {
  const mid = Math.floor((start + end) / 2);

  if (val === arr[mid]) {
    return mid;
  }

  if (start >= end) {
    return -1;
  }

  return val < arr[mid]
    ? binarySearch(arr, val, start, mid - 1)
    : binarySearch(arr, val, mid + 1, end);
}

𝗬𝗼𝘂 𝘄𝗮𝗻𝘁 𝘀𝗽𝗲𝗲𝗱？𝗥𝗲𝗮𝗱 𝘁𝗵𝗶𝘀。

正确实现的二元搜索（不修改数组、制作数组的浅拷贝或其他荒谬）的平均复杂度约为O(k*log ₂ (n))（其中 k 是常数表示不必要的开销）。假设您有一个包含 1024 个元素的数组，在这种情况下常数 k 为 1。使用线性搜索，平均复杂度为O(k*n/2)=O(1*1024/2)=O(512)。使用二分搜索，您的复杂度为O(k*log ₂ (n))=O(1*log ₂ (1024))=O(1*10)=O(10)。现在，假设您使线性搜索算法的速度提高了 25%，而二分搜索算法的速度提高了 25%。现在，这两种算法的 k 都是 0.75。线性搜索的复杂度降低到O(384)（获得 128 个性能点），而二分搜索降低到O(7.5)（仅获得 2.5 个性能点）。优化二分搜索方法的这种最小收益是因为二分搜索方法已经非常快了。因此，任何理智的人都应该更倾向于在尝试优化二分搜索算法之前优化程序的其余部分。尽管有这种清晰的推理，我最终还是屈服于诱惑，将二分搜索功能优化到 JavaScript 工程的绝对限制。

为了开始性能最大值，让我们首先研究我开始使用的初始函数。此函数可能比页面下方显示的函数慢得多（它仍然比此处发布的任何其他答案快得多），但应该不那么令人困惑。

const sArr = [0,4,5,6,9,13,14,21,27,44];
const s = sArr[Math.random() * sArr.length | 0];
document.body.innerHTML = s+" is at "+slowestBS(sArr, s);

function slowestBS(array, searchedValue, ARG_start, ARG_len){
  // Range of [start, start+len): only start is inclusive. It works
  // similarly to "...".substr(start, len).indexOf(sValue)
  // `void 0` is shorthand for `undefined`
  var start = ARG_start |0;
  var len = (ARG_len === void 0 ? (array.length|0)-start : ARG_len) | 0;
  len = len - 1 |0;
  for (let i=0x80000000; i; i >>>= 1) {
    if (len & i) {
      const withoutCurBit = len & ~(i-1);
      if (array[start + withoutCurBit] > searchedValue) {
        len = withoutCurBit - 1 |0;
      }
    }
  }
  if (array[start+len] !== searchedValue) {
    // remove this if-statement to return the next closest
    // element going downwards from the searched-for value
    // OR 0 if the value is less than all values in the
    // array. https://stackoverflow.com/a/44981570/5601591
    return -1 - start - len |0;
  }
  return start + len |0;
}

上述函数的返回值如下。

如果找到该值，则返回该值的索引。
如果未找到该值，则它返回-1 - nearestIndex其中的nearestIndex 是找到的索引，该索引是最接近的数字 <= index 并且上限为 0。
如果数组没有在指定范围内排序，那么它将返回一些无意义的数字。

为了开始优化，让我们首先删除那个讨厌的内部 if 分支。

const sArr = [0,4,5,6,9,13,14,21,27,44];
const s = sArr[Math.random() * sArr.length | 0];
document.body.innerHTML = s+" is at "+compactBS(sArr, s);

function compactBS(array, searchedValue, ARG_start, ARG_len){
  // `void 0` is shorthand for `undefined`
  var start = ARG_start === void 0 ? 0 : ARG_start |0;
  var len = (ARG_len === void 0 ? (array.length|0) - start : ARG_len) |0;
  len = len - 1 | 0;
  for (let i=0x80000000; i; i >>>= 1) {
    if (len & i) {
      const noCBit = len & ~(i-1);
      // noCBits now contains all the bits in len that are
      // greater than the present value of i.
      len ^= (
        (len ^ (noCBit-1)) & 
        ((array[start+noCBit] <= searchedValue |0) - 1 >>>0)
      ); // works based on the logic that `(x^y)^x === y` is always true
    }
  }
  if (array[start+len] !== searchedValue) {
    // remove this if-statement to return the next closest
    // element going downwards from the searched-for value
    // OR 0 if the value is less than all values in the
    // array. https://stackoverflow.com/a/44981570/5601591
    return -1 - start - len |0;
  }
  return start + len |0;
}

现在，然后，展开它，预先计算它，使其快速、美观和良好，就像这样：

const sArr = [0,4,5,6,9,13,14,21,27,44];
const s = sArr[Math.random() * sArr.length | 0];
document.body.innerHTML = s+" is at "+goodBinarySearch(sArr, s);

function goodBinarySearch(array, sValue, ARG_start, ARG_len){
  // Range of [start, start+len): only start is inclusive. It works
  // similarly to "...".substr(start, len).indexOf(sValue)
  // `void 0` is shorthand for `undefined`
  var start = (ARG_start === void 0 ? 0 : ARG_start) | 0;
  var len = (ARG_len === void 0 ? (array.length|0) - start : ARG_len) |0;
  len = len - 1 |0;
  
  if (len & 0x80000000) {
    const nCB = len & 0x80000000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x40000000) {
    const nCB = len & 0xc0000000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x20000000) {
    const nCB = len & 0xe0000000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x10000000) {
    const nCB = len & 0xf0000000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x8000000) {
    const nCB = len & 0xf8000000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x4000000) {
    const nCB = len & 0xfc000000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x2000000) {
    const nCB = len & 0xfe000000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x1000000) {
    const nCB = len & 0xff000000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x800000) {
    const nCB = len & 0xff800000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x400000) {
    const nCB = len & 0xffc00000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x200000) {
    const nCB = len & 0xffe00000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x100000) {
    const nCB = len & 0xfff00000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x80000) {
    const nCB = len & 0xfff80000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x40000) {
    const nCB = len & 0xfffc0000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x20000) {
    const nCB = len & 0xfffe0000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x10000) {
    const nCB = len & 0xffff0000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x8000) {
    const nCB = len & 0xffff8000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x4000) {
    const nCB = len & 0xffffc000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x2000) {
    const nCB = len & 0xffffe000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x1000) {
    const nCB = len & 0xfffff000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x800) {
    const nCB = len & 0xfffff800;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x400) {
    const nCB = len & 0xfffffc00;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x200) {
    const nCB = len & 0xfffffe00;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x100) {
    const nCB = len & 0xffffff00;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x80) {
    const nCB = len & 0xffffff80;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x40) {
    const nCB = len & 0xffffffc0;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x20) {
    const nCB = len & 0xffffffe0;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x10) {
    const nCB = len & 0xfffffff0;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x8) {
    const nCB = len & 0xfffffff8;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x4) {
    const nCB = len & 0xfffffffc;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x2) {
    const nCB = len & 0xfffffffe;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x1) {
    const nCB = len & 0xffffffff;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (array[start+len|0] !== sValue) {
    // remove this if-statement to return the next closest
    // element going downwards from the searched-for value
    // OR 0 if the value is less than all values in the
    // array. https://stackoverflow.com/a/44981570/5601591
    return -1 - start - len |0;
  }
  return start + len |0;
}

但是等等... 分裂的耳语是更高性能的前夜。很可能，您正在紧密循环中调用二分查找。在这种情况下，我们可以预先计算将实际处理的第一个值，并使用高性能整数索引 switch 语句直接跳到它。但是，在使用它时，您必须确保在修改数组长度后永远不要重用生成的快速函数，因为这样只会搜索数组的一部分。

const clz32 = Math.clz32 || (function(log, LN2){
  return function(x) {
    return 31 - log(x >>> 0) / LN2 | 0; // the "| 0" acts like math.floor
  };
})(Math.log, Math.LN2);

const sArr = [0,4,5,6,9,13,14,21,27,44];
const compFunc = fastestBS(sArr);
for (var i=0,str="",len=sArr.length|0; i < len; i=i+1|0)
  str += sArr[i]+" is at "+compFunc(sArr[i])+"<br/>";
document.body.innerHTML = str; // show the result

function fastestBS(array, ARG_start, ARG_initLen){
  // Range of [start, start+len): only start is inclusive. It works
  // similarly to "...".substr(start, len).indexOf(sValue)
  // `void 0` is shorthand for `undefined`
  var start = ARG_start === void 0 ? 0 : ARG_start |0;
  var initLen = (ARG_initLen===void 0 ? (array.length|0)-start : ARG_initLen) |0;
  initLen = initLen - 1 |0;
  const compGoto = clz32(initLen) & 31;
  return function(sValue) {
    var len = initLen | 0;
    switch (compGoto) {
      case 0:
        if (len & 0x80000000) {
          const nCB = len & 0x80000000;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 1:
        if (len & 0x40000000) {
          const nCB = len & 0xc0000000;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 2:
        if (len & 0x20000000) {
          const nCB = len & 0xe0000000;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 3:
        if (len & 0x10000000) {
          const nCB = len & 0xf0000000;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 4:
        if (len & 0x8000000) {
          const nCB = len & 0xf8000000;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 5:
        if (len & 0x4000000) {
          const nCB = len & 0xfc000000;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 6:
        if (len & 0x2000000) {
          const nCB = len & 0xfe000000;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 7:
        if (len & 0x1000000) {
          const nCB = len & 0xff000000;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 8:
        if (len & 0x800000) {
          const nCB = len & 0xff800000;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 9:
        if (len & 0x400000) {
          const nCB = len & 0xffc00000;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 10:
        if (len & 0x200000) {
          const nCB = len & 0xffe00000;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 11:
        if (len & 0x100000) {
          const nCB = len & 0xfff00000;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 12:
        if (len & 0x80000) {
          const nCB = len & 0xfff80000;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 13:
        if (len & 0x40000) {
          const nCB = len & 0xfffc0000;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 14:
        if (len & 0x20000) {
          const nCB = len & 0xfffe0000;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 15:
        if (len & 0x10000) {
          const nCB = len & 0xffff0000;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 16:
        if (len & 0x8000) {
          const nCB = len & 0xffff8000;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 17:
        if (len & 0x4000) {
          const nCB = len & 0xffffc000;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 18:
        if (len & 0x2000) {
          const nCB = len & 0xffffe000;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 19:
        if (len & 0x1000) {
          const nCB = len & 0xfffff000;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 20:
        if (len & 0x800) {
          const nCB = len & 0xfffff800;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 21:
        if (len & 0x400) {
          const nCB = len & 0xfffffc00;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 22:
        if (len & 0x200) {
          const nCB = len & 0xfffffe00;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 23:
        if (len & 0x100) {
          const nCB = len & 0xffffff00;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 24:
        if (len & 0x80) {
          const nCB = len & 0xffffff80;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 25:
        if (len & 0x40) {
          const nCB = len & 0xffffffc0;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 26:
        if (len & 0x20) {
          const nCB = len & 0xffffffe0;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 27:
        if (len & 0x10) {
          const nCB = len & 0xfffffff0;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 28:
        if (len & 0x8) {
          const nCB = len & 0xfffffff8;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 29:
        if (len & 0x4) {
          const nCB = len & 0xfffffffc;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 30:
        if (len & 0x2) {
          const nCB = len & 0xfffffffe;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 31:
        if (len & 0x1) {
          const nCB = len & 0xffffffff;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }

    }
    if (array[start+len|0] !== sValue) {
      // remove this if-statement to return the next closest
      // element going downwards from the searched-for value
      // OR 0 if the value is less than all values in the
      // array. https://stackoverflow.com/a/44981570/5601591
      return -1 - start - len |0;
    }
    return start + len |0;
  };
}

演示：

(function(document){"use strict";
var textarea = document.getElementById('inputbox'),
    searchinput = document.getElementById('search'),
    searchStart = document.getElementById('start'),
    searchedLength = document.getElementById('length'),
    resultbox = document.getElementById('result'),
    timeoutID = -1;
function doUpdate(){
   try {
      var txt = textarea.value.replace(/\s*\[|\]\s*/g, '').split(',');
      var arr = JSON.parse(textarea.value);
      var searchval = JSON.parse(searchinput.value);
      var textmtchs = textarea.value.match(/\s*\[|\]\s*/g);
      var start = searchStart.value || void 0;
      var sub = searchedLength.value || void 0;
      
      txt = refSort(txt, arr);
      textarea.value = textmtchs[0] +
                        txt.join(',') +
                       textmtchs[textmtchs.length-1];
      arr = JSON.parse(textarea.value);
      resultbox.value = goodBinarySearch(arr, searchval, start, sub);
   } catch(e) {
      resultbox.value = 'Error';
   }
}
textarea.oninput = searchinput.oninput = 
    searchStart.oninput = searchedLength.oninput =
    textarea.onkeyup = searchinput.onkeyup = 
    searchStart.onkeyup = searchedLength.onkeyup = 
    textarea.onchange = searchinput.onchange = 
    searchStart.onchange = searchedLength.onchange = function(e){
  clearTimeout( timeoutID );
  timeoutID = setTimeout(doUpdate, e.target === textarea ? 384 : 125);
}

function refSort(targetData, refData) {
  var indices = Object.keys(refData);
  indices.sort(function(indexA, indexB) {
    if (refData[indexA] < refData[indexB]) return -1;
    if (refData[indexA] > refData[indexB]) return 1;
    return 0;
  });
  return indices.map(function(i){ return targetData[i] })
}
function goodBinarySearch(array, sValue, ARG_start, ARG_len){
  // Range of [start, start+len): only start is inclusive. It works
  // similarly to "...".substr(start, len).indexOf(sValue)
  // `void 0` is shorthand for `undefined`
  var start = (ARG_start === void 0 ? 0 : ARG_start) | 0;
  var len = (ARG_len === void 0 ? (array.length|0) - start : ARG_len) |0;
  len = len - 1 |0;
  
  if (len & 0x80000000) {
    const nCB = len & 0x80000000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x40000000) {
    const nCB = len & 0xc0000000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x20000000) {
    const nCB = len & 0xe0000000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x10000000) {
    const nCB = len & 0xf0000000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x8000000) {
    const nCB = len & 0xf8000000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x4000000) {
    const nCB = len & 0xfc000000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x2000000) {
    const nCB = len & 0xfe000000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x1000000) {
    const nCB = len & 0xff000000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x800000) {
    const nCB = len & 0xff800000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x400000) {
    const nCB = len & 0xffc00000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x200000) {
    const nCB = len & 0xffe00000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x100000) {
    const nCB = len & 0xfff00000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x80000) {
    const nCB = len & 0xfff80000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x40000) {
    const nCB = len & 0xfffc0000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x20000) {
    const nCB = len & 0xfffe0000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x10000) {
    const nCB = len & 0xffff0000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x8000) {
    const nCB = len & 0xffff8000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x4000) {
    const nCB = len & 0xffffc000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x2000) {
    const nCB = len & 0xffffe000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x1000) {
    const nCB = len & 0xfffff000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x800) {
    const nCB = len & 0xfffff800;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x400) {
    const nCB = len & 0xfffffc00;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x200) {
    const nCB = len & 0xfffffe00;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x100) {
    const nCB = len & 0xffffff00;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x80) {
    const nCB = len & 0xffffff80;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x40) {
    const nCB = len & 0xffffffc0;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x20) {
    const nCB = len & 0xffffffe0;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x10) {
    const nCB = len & 0xfffffff0;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x8) {
    const nCB = len & 0xfffffff8;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x4) {
    const nCB = len & 0xfffffffc;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x2) {
    const nCB = len & 0xfffffffe;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x1) {
    const nCB = len & 0xffffffff;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (array[start+len|0] !== sValue) {
    // remove this if-statement to return the next closest
    // element going downwards from the searched-for value
    // OR 0 if the value is less than all values in the
    // array. https://stackoverflow.com/a/44981570/5601591
    return -1 - start - len |0;
  }
  return start + len |0;
}
})(document);

<h3 style="margin:.125em;width:100%;text-align:center">The Array (Must Be A Valid JSON Array)</h3>
<textarea placeholder="[-24, -12, 0, 0, 9, 16, 18, 64, 80]" type="text" rows=6 style="width:calc(100% - .5em);display:block" id="inputbox">[-24, -12, 0, 0, 9, 16, 18, 64, 80]</textarea>

<table style="table-layout:fixed;font-size:1.2em" width="100%"><tbody>
  <tr>
    <td colspan="3">Search Value: <input type="text" id="search" value="-12" style="width:8em;text-align:center;float:right" /></td>
    <td></td>
    <td colspan="3">Resulting Index: <input type="text" id="result" value="1" style="width:8em;text-align:center;float:right" readonly="" />
  </tr>
  <tr>
    <td colspan="3">Start Index: <input type="text" id="start" value="" placeholder="(0)" style="width:8em;text-align:center;float:right" /></td>
    <td></td>
    <td colspan="3">Searched Length: <input type="text" id="length" value="" placeholder="(array length)" style="width:8em;text-align:center;float:right" />
  </tr>
</tbody></table>

您还可以在演示中使用字符串数组（用引号括起来），它应该可以正常工作。要搜索字符串，您必须在搜索值周围加上引号。

@Joki 是的，您是正确的，如果您undefined在空数组 ( []) 中搜索，那么它将返回0而不是-1。但是，我怀疑很多人（如果有的话）undefined用来存储值。因此，我怀疑是否会使用额外检查所需的额外开销。

2021-03-18 14:50:37

@joki 任意比较函数在 javascript 中很慢（除非本机实现），因为每次调用任何函数时，函数的上下文都必须被推入堆栈，然后在函数完成执行后从堆栈中弹出。这种不断推动/弹出每一步的效率相当低。

2021-03-19 14:50:37

关于上述代码的警告：如果使用空数组调用，它将访问最后一行的第一个元素数组 [0]，这可能会导致不良行为......

2021-03-21 14:50:37

我只想指出我的版本被指定为返回array.length一个空数组。你可以return lo，如果你喜欢！预解码（数组[1]）&&预解码（阵列[1 + 1]），无需额外的（昂贵的）比较。hi + lo您的代码中的术语可能会溢出，这是惯用语避免的lo + ((hi - lo) >> 1)。我认为if … else比continue+ 标签更具可读性；)。我的版本支持任意比较函子，它只能比较部分数据等。;)

2021-03-24 14:50:37

……这正是二分搜索比线性搜索表现更好的原因——与线性搜索相比，前者只进行对数次数的比较，如果比较代价高昂，这可能会产生很大的不同。在不改变渐近复杂性的情况下修复搜索算法中的比较使其通用性降低，因此大量数据的预期加速要小得多。

2021-04-08 14:50:37

其它你可能感兴趣的问题

上一篇JavaScript 代码技巧：foo.x 的值是什么下一篇检测到双击事件时需要取消单击/鼠标向上事件