在Javascript中的二分查找

Question

在Javascript中的二分查找

76

我正在尝试在JavaScript中实现二分查找算法。似乎没什么问题，但我的返回语句似乎返回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);

- 4m1r

1

另外，为什么arr.splice会修改'a'的值？ - 4m1r

3

要返回递归状态，你需要在每个情况下使用return binarySearch（...）。 - cmbuckley

Splice修改原始数组，参见W3Schools；这包括它通过引用传递。一个好的起点是http://www.nczonline.net/blog/2009/06/09/computer-science-in-javascript-binary-search-tree-part-1/。 - Sunny Patel

它被标记为不太可能对未来的访问者有帮助，因为它只是一个小错误。 - cmbuckley

2

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

28个回答

49

二分查找 (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);
}

- Lior Elrom

37

这个问题有很多可行的解决方案，但是它们都会在找到匹配项后立即返回。虽然这可能对性能有小幅正面影响，但由于二分查找的对数特性，这是可以忽略不计的，如果比较函数计算代价昂贵，则实际上会损害性能。

此外，它还阻止了二分查找算法的一个非常有用的应用：查找匹配元素的范围，也称为查找下限或上限。

以下实现返回索引0≤i≤array.length，使得给定谓词对于array[i-1]为false，对于array[i]为true。如果在任何地方谓词都是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 === hi时终止，这意味着!pred(array[hi - 1]) && pred(array[hi])，这是期望的后置条件。

如果使用比较函数compare对数组进行sort()排序，则函数在调用时返回项目的最小插入位置。

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);
}

当数组中包含多个元素进行比较时，这是最有用的，例如，元素包含不属于排序条件的其他数据。

- joki

1

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

1

@Nolo 是的，const 是语义化的 - 但是你的推理方式是错误的 ;) 当然 let 也可以工作，因为它更宽松，但在这里严格的 const 就足够了。 - joki

1

@Nolo在这种简单的情况下，编译器可以证明变量永远不会被重新赋值，所以我不认为这会有任何影响。但我仍然认为养成这个好习惯是很重要的 ;) - joki

1

lo + ((hi - lo) >> 1) 相对于 (hi + lo) >> 1 有什么优势？ - Dominic

1

@dominic 发现得很好，提出了非常好的问题！当元素数量超过整数类型范围的一半时，(hi + lo)就会溢出。这是这些类型计算中众所周知的问题，例如请参见 https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html - joki

显示剩余9条评论

27

您没有显式返回递归内部调用（即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 {
// ...

查看工作示例

- Eliran Malka

1

太棒了，谢谢。我猜，修改原始数组也没关系吧？ - 4m1r

1

好的，这取决于你。如果你想避免传递的数组被改变，可以事先克隆它（例如 var _arr = arr.slice(0)）。这里有一个相关的 JSFiddle。 - Eliran Malka

18

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

2

我建议你修改这个答案，使用slice而非splice。我们不希望一个搜索函数去改变它所操作的数据。我会建议使用binarySearch(arr.slice(mid), i)和 binarySearch(arr.slice(0, mid), i)。 - porkbrain

1

@gb96，@MichaelBausano，我只是更新了原帖中的代码来解决他们所指出的问题，返回值和 splice 的不纯性似乎与此问题无关，所以我将它们保留原样，以免混淆答案。 - Eliran Malka

21

如何正确实现二分查找算法

正确实现二分查找算法的平均复杂度约为 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%。现在，两个算法的常数都是 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 "+compactBS(sArr, s);

function compactBS(array, searchedValue, ARG_start, ARG_len){
  // `void 0` is shorthand for `undefined`
  // 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)|0;
  var offset = 0;

  for (var i=30; i >= 0; i=i-1|0) {
    offset = start + ((1<<i) - 1|0)|0;
    if (offset < len) {
      start = start + ((array[offset] < searchedValue) << i) | 0;
    }
  }

  if (array[start|0] !== 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://dev59.com/EGEh5IYBdhLWcg3wMA_M#44981570
    return -1 - start |0;
  }
  return start |0;
}

上述函数的返回值如下：

如果找到了该值，则返回该值的索引。
如果未找到该值，则返回-1-nearestIndex，其中nearestIndex是找到的最接近该值的索引，但不能小于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 index "+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 | 0;
  var len = ARG_len === void 0 ? (array.length|0) - start |0 : ARG_len|0;
  var offset = 0;

  if ((offset = start + 0x3fffffff|0) < len) {
    start = start + ((array[offset] < sValue) << 30) | 0;
  }
  if ((offset = start + 0x1fffffff|0) < len) {
    start = start + ((array[offset] < sValue) << 29) | 0;
  }
  if ((offset = start + 0x0fffffff|0) < len) {
    start = start + ((array[offset] < sValue) << 28) | 0;
  }
  if ((offset = start + 0x07ffffff|0) < len) {
    start = start + ((array[offset] < sValue) << 27) | 0;
  }
  if ((offset = start + 0x03ffffff|0) < len) {
    start = start + ((array[offset] < sValue) << 26) | 0;
  }
  if ((offset = start + 0x01ffffff|0) < len) {
    start = start + ((array[offset] < sValue) << 25) | 0;
  }
  if ((offset = start + 0x00ffffff|0) < len) {
    start = start + ((array[offset] < sValue) << 24) | 0;
  }
  if ((offset = start + 0x007fffff|0) < len) {
    start = start + ((array[offset] < sValue) << 23) | 0;
  }
  if ((offset = start + 0x003fffff|0) < len) {
    start = start + ((array[offset] < sValue) << 22) | 0;
  }
  if ((offset = start + 0x001fffff|0) < len) {
    start = start + ((array[offset] < sValue) << 21) | 0;
  }
  if ((offset = start + 0x000fffff|0) < len) {
    start = start + ((array[offset] < sValue) << 20) | 0;
  }
  if ((offset = start + 0x0007ffff|0) < len) {
    start = start + ((array[offset] < sValue) << 19) | 0;
  }
  if ((offset = start + 0x0003ffff|0) < len) {
    start = start + ((array[offset] < sValue) << 18) | 0;
  }
  if ((offset = start + 0x0001ffff|0) < len) {
    start = start + ((array[offset] < sValue) << 17) | 0;
  }
  if ((offset = start + 0x0000ffff|0) < len) {
    start = start + ((array[offset] < sValue) << 16) | 0;
  }
  if ((offset = start + 0x00007fff|0) < len) {
    start = start + ((array[offset] < sValue) << 15) | 0;
  }
  if ((offset = start + 0x00003fff|0) < len) {
    start = start + ((array[offset] < sValue) << 14) | 0;
  }
  if ((offset = start + 0x00001fff|0) < len) {
    start = start + ((array[offset] < sValue) << 13) | 0;
  }
  if ((offset = start + 0x00000fff|0) < len) {
    start = start + ((array[offset] < sValue) << 12) | 0;
  }
  if ((offset = start + 0x000007ff|0) < len) {
    start = start + ((array[offset] < sValue) << 11) | 0;
  }
  if ((offset = start + 0x000003ff|0) < len) {
    start = start + ((array[offset] < sValue) << 10) | 0;
  }
  if ((offset = start + 0x000001ff|0) < len) {
    start = start + ((array[offset] < sValue) << 9) | 0;
  }
  if ((offset = start + 0x000000ff|0) < len) {
    start = start + ((array[offset] < sValue) << 8) | 0;
  }
  if ((offset = start + 0x0000007f|0) < len) {
    start = start + ((array[offset] < sValue) << 7) | 0;
  }
  if ((offset = start + 0x0000003f|0) < len) {
    start = start + ((array[offset] < sValue) << 6) | 0;
  }
  if ((offset = start + 0x0000001f|0) < len) {
    start = start + ((array[offset] < sValue) << 5) | 0;
  }
  if ((offset = start + 0x0000000f|0) < len) {
    start = start + ((array[offset] < sValue) << 4) | 0;
  }
  if ((offset = start + 0x00000007|0) < len) {
    start = start + ((array[offset] < sValue) << 3) | 0;
  }
  if ((offset = start + 0x00000003|0) < len) {
    start = start + ((array[offset] < sValue) << 2) | 0;
  }
  if ((offset = start + 0x00000001|0) < len) {
    start = start + ((array[offset] < sValue) << 1) | 0;
  }
  if (start < len) {
    start = start + ((array[start] < sValue) << 0) | 0;
  }

  if (array[start|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://dev59.com/EGEh5IYBdhLWcg3wMA_M#44981570
    return -1 - start |0;
  }
  return start |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 index "+fastBinarySearch(sArr, s);

function fastBinarySearch(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 | 0;
  var len = ARG_len === void 0 ? (array.length|0) - start |0 : ARG_len|0;
  var offset = 0, nCB = 0;

  if ((start + 0x00007fff|0) < len) {
    if ((start + 0x007fffff|0) < len) {
      if ((start + 0x07ffffff|0) < len) {
        if ((start + 0x1fffffff|0) < len) {
          if ((offset = start + 0x3fffffff|0) < len) {
            start = start + ((array[offset] < sValue) << 30) | 0;
          }
          if ((offset = start + 0x1fffffff|0) < len) {
            start = start + ((array[offset] < sValue) << 29) | 0;
          }
        }
        if ((offset = start + 0x0fffffff|0) < len) {
          start = start + ((array[offset] < sValue) << 28) | 0;
        }
        if ((offset = start + 0x07ffffff|0) < len) {
          start = start + ((array[offset] < sValue) << 27) | 0;
        }
      }
      if ((start + 0x01ffffff|0) < len) {
        if ((offset = start + 0x03ffffff|0) < len) {
          start = start + ((array[offset] < sValue) << 26) | 0;
        }
        if ((offset = start + 0x01ffffff|0) < len) {
          start = start + ((array[offset] < sValue) << 25) | 0;
        }
      }
      if ((offset = start + 0x00ffffff|0) < len) {
        start = start + ((array[offset] < sValue) << 24) | 0;
      }
      if ((offset = start + 0x007fffff|0) < len) {
        start = start + ((array[offset] < sValue) << 23) | 0;
      }
    }
    if ((start + 0x0007ffff|0) < len) {
      if ((start + 0x001fffff|0) < len) {
        if ((offset = start + 0x003fffff|0) < len) {
          start = start + ((array[offset] < sValue) << 22) | 0;
        }
        if ((offset = start + 0x001fffff|0) < len) {
          start = start + ((array[offset] < sValue) << 21) | 0;
        }
      }
      if ((offset = start + 0x000fffff|0) < len) {
        start = start + ((array[offset] < sValue) << 20) | 0;
      }
      if ((offset = start + 0x0007ffff|0) < len) {
        start = start + ((array[offset] < sValue) << 19) | 0;
      }
    }
    if ((start + 0x0001ffff|0) < len) {
      if ((offset = start + 0x0003ffff|0) < len) {
        start = start + ((array[offset] < sValue) << 18) | 0;
      }
      if ((offset = start + 0x0001ffff|0) < len) {
        start = start + ((array[offset] < sValue) << 17) | 0;
      }
    }
    if ((offset = start + 0x0000ffff|0) < len) {
      start = start + ((array[offset] < sValue) << 16) | 0;
    }
    if ((offset = start + 0x00007fff|0) < len) {
      start = start + ((array[offset] < sValue) << 15) | 0;
    }
  }
  if ((start + 0x0000007f|0) < len) {
    if ((start + 0x000007ff|0) < len) {
      if ((start + 0x00001fff|0) < len) {
        if ((offset = start + 0x00003fff|0) < len) {
          start = start + ((array[offset] < sValue) << 14) | 0;
        }
        if ((offset = start + 0x00001fff|0) < len) {
          start = start + ((array[offset] < sValue) << 13) | 0;
        }
      }
      if ((offset = start + 0x00000fff|0) < len) {
        start = start + ((array[offset] < sValue) << 12) | 0;
      }
      if ((offset = start + 0x000007ff|0) < len) {
        start = start + ((array[offset] < sValue) << 11) | 0;
      }
    }
    if ((start + 0x000001ff|0) < len) {
      if ((offset = start + 0x000003ff|0) < len) {
        start = start + ((array[offset] < sValue) << 10) | 0;
      }
      if ((offset = start + 0x000001ff|0) < len) {
        start = start + ((array[offset] < sValue) << 9) | 0;
      }
    }
    if ((offset = start + 0x000000ff|0) < len) {
      start = start + ((array[offset] < sValue) << 8) | 0;
    }
    if ((offset = start + 0x0000007f|0) < len) {
      start = start + ((array[offset] < sValue) << 7) | 0;
    }
  }
  if ((start + 0x00000007|0) < len) {
    if ((start + 0x0000001f|0) < len) {
      if ((offset = start + 0x0000003f|0) < len) {
        start = start + ((array[offset] < sValue) << 6) | 0;
      }
      if ((offset = start + 0x0000001f|0) < len) {
        start = start + ((array[offset] < sValue) << 5) | 0;
      }
    }
    if ((offset = start + 0x0000000f|0) < len) {
      start = start + ((array[offset] < sValue) << 4) | 0;
    }
    if ((offset = start + 0x00000007|0) < len) {
      start = start + ((array[offset] < sValue) << 3) | 0;
    }
  }

  offset = start + 0x00000003|0;
  nCB = -(offset < len|0) | 0;
  start = start + (((array[offset & nCB] < sValue) << 2) & nCB) | 0;

  offset = start + 0x00000001|0;
  nCB = -(offset < len|0) | 0;
  start = start + (((array[offset & nCB] < sValue) << 1) & nCB) | 0;

  offset = start;
  nCB = -(offset < len|0) | 0;
  start = start + ((array[offset & nCB] < sValue) & nCB) | 0;

  if (array[start|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://dev59.com/EGEh5IYBdhLWcg3wMA_M#44981570
    return -1 - start |0;
  }
  
  return start |0;
}

但是等等……更好的性能正在暗中窃喜。也许您正在一个紧密的循环中调用二分搜索。在这种情况下，我们可以预计算实际将被处理的第一个值，并使用高性能的整数索引开关语句跳过它。然而，在使用此功能时，必须确保在修改数组长度后永远不要重复使用生成的快速函数，因为那样只会搜索部分数组。

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 ArrayProtoSlice = Array.prototype.slice;

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_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 init_start = ARG_start | 0;
  var len = ARG_len === void 0 ? array.length|0 : init_start+(ARG_len|0)|0;
  const compGoto = clz32(len) & 31;

  var arrPadded = array;
  var relLen = len - init_start | 0;
  if (relLen & (relLen - 1)) { // if its not a power of 2
    var sizeUp = relLen;
    sizeUp |= sizeUp >>> 16;
    sizeUp |= sizeUp >>> 8;
    sizeUp |= sizeUp >>> 4;
    sizeUp |= sizeUp >>> 2;
    sizeUp |= sizeUp >>> 1;
    sizeUp = sizeUp + 1 - relLen | 0;

    arrPadded = ArrayProtoSlice.call(array);

    var accCur = [array[len - 1 | 0]];
    while (1 < sizeUp && accCur.length < 65536) {
      if (sizeUp & 1) arrPadded.push.apply(arrPadded, accCur);
      sizeUp >>>= 1;
      accCur.push.apply(accCur, accCur);
    }
    for (var i=0; i < sizeUp; i=i+1|0) {
      arrPadded.push.apply(arrPadded, accCur);
    }
  }

  return function(sValue) {
    var start = init_start | 0, offset = 0;
    switch (compGoto) {
      case 1:
        start = start + ((arrPadded[start + 0x3fffffff|0] < sValue) << 30) | 0;
      case 2:
        start = start + ((arrPadded[start + 0x1fffffff|0] < sValue) << 29) | 0;
      case 3:
        start = start + ((arrPadded[start + 0x0fffffff|0] < sValue) << 28) | 0;
      case 4:
        start = start + ((arrPadded[start + 0x07ffffff|0] < sValue) << 27) | 0;
      case 5:
        start = start + ((arrPadded[start + 0x03ffffff|0] < sValue) << 26) | 0;
      case 6:
        start = start + ((arrPadded[start + 0x01ffffff|0] < sValue) << 25) | 0;
      case 7:
        start = start + ((arrPadded[start + 0x00ffffff|0] < sValue) << 24) | 0;
      case 8:
        start = start + ((arrPadded[start + 0x007fffff|0] < sValue) << 23) | 0;
      case 9:
        start = start + ((arrPadded[start + 0x003fffff|0] < sValue) << 22) | 0;
      case 10:
        start = start + ((arrPadded[start + 0x001fffff|0] < sValue) << 21) | 0;
      case 11:
        start = start + ((arrPadded[start + 0x000fffff|0] < sValue) << 20) | 0;
      case 12:
        start = start + ((arrPadded[start + 0x0007ffff|0] < sValue) << 19) | 0;
      case 13:
        start = start + ((arrPadded[start + 0x0003ffff|0] < sValue) << 18) | 0;
      case 14:
        start = start + ((arrPadded[start + 0x0001ffff|0] < sValue) << 17) | 0;
      case 15:
        start = start + ((arrPadded[start + 0x0000ffff|0] < sValue) << 16) | 0;
      case 16:
        start = start + ((arrPadded[start + 0x00007fff|0] < sValue) << 15) | 0;
      case 17:
        start = start + ((arrPadded[start + 0x00003fff|0] < sValue) << 14) | 0;
      case 18:
        start = start + ((arrPadded[start + 0x00001fff|0] < sValue) << 13) | 0;
      case 19:
        start = start + ((arrPadded[start + 0x00000fff|0] < sValue) << 12) | 0;
      case 20:
        start = start + ((arrPadded[start + 0x000007ff|0] < sValue) << 11) | 0;
      case 21:
        start = start + ((arrPadded[start + 0x000003ff|0] < sValue) << 10) | 0;
      case 22:
        start = start + ((arrPadded[start + 0x000001ff|0] < sValue) << 9) | 0;
      case 23:
        start = start + ((arrPadded[start + 0x000000ff|0] < sValue) << 8) | 0;
      case 24:
        start = start + ((arrPadded[start + 0x0000007f|0] < sValue) << 7) | 0;
      case 25:
        start = start + ((arrPadded[start + 0x0000003f|0] < sValue) << 6) | 0;
      case 26:
        start = start + ((arrPadded[start + 0x0000001f|0] < sValue) << 5) | 0;
      case 27:
        start = start + ((arrPadded[start + 0x0000000f|0] < sValue) << 4) | 0;
      case 28:
        start = start + ((arrPadded[start + 0x00000007|0] < sValue) << 3) | 0;
      case 29:
        start = start + ((arrPadded[start + 0x00000003|0] < sValue) << 2) | 0;
      case 30:
        start = start + ((arrPadded[start + 0x00000001|0] < sValue) << 1) | 0;
      case 31:
        start = start + ((arrPadded[start] < sValue) << 0) | 0;
    }
    if (arrPadded[start|0] !== sValue) {
      if (len <= start) start = len - 1 | 0; // because we padd the array up to the next power of 2
      // 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://dev59.com/EGEh5IYBdhLWcg3wMA_M#44981570
      return -1 - start |0;
    }
    return start;
  };
}

演示：

(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 = fastBinarySearch(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 fastBinarySearch(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 | 0;
  var len = ARG_len === void 0 ? (array.length|0) - start |0 : ARG_len|0;
  var offset = 0, nCB = 0;

  if ((start + 0x00007fff|0) < len) {
    if ((start + 0x007fffff|0) < len) {
      if ((start + 0x07ffffff|0) < len) {
        if ((start + 0x1fffffff|0) < len) {
          if ((offset = start + 0x3fffffff|0) < len) {
            start = start + ((array[offset] < sValue) << 30) | 0;
          }
          if ((offset = start + 0x1fffffff|0) < len) {
            start = start + ((array[offset] < sValue) << 29) | 0;
          }
        }
        if ((offset = start + 0x0fffffff|0) < len) {
          start = start + ((array[offset] < sValue) << 28) | 0;
        }
        if ((offset = start + 0x07ffffff|0) < len) {
          start = start + ((array[offset] < sValue) << 27) | 0;
        }
      }
      if ((start + 0x01ffffff|0) < len) {
        if ((offset = start + 0x03ffffff|0) < len) {
          start = start + ((array[offset] < sValue) << 26) | 0;
        }
        if ((offset = start + 0x01ffffff|0) < len) {
          start = start + ((array[offset] < sValue) << 25) | 0;
        }
      }
      if ((offset = start + 0x00ffffff|0) < len) {
        start = start + ((array[offset] < sValue) << 24) | 0;
      }
      if ((offset = start + 0x007fffff|0) < len) {
        start = start + ((array[offset] < sValue) << 23) | 0;
      }
    }
    if ((start + 0x0007ffff|0) < len) {
      if ((start + 0x001fffff|0) < len) {
        if ((offset = start + 0x003fffff|0) < len) {
          start = start + ((array[offset] < sValue) << 22) | 0;
        }
        if ((offset = start + 0x001fffff|0) < len) {
          start = start + ((array[offset] < sValue) << 21) | 0;
        }
      }
      if ((offset = start + 0x000fffff|0) < len) {
        start = start + ((array[offset] < sValue) << 20) | 0;
      }
      if ((offset = start + 0x0007ffff|0) < len) {
        start = start + ((array[offset] < sValue) << 19) | 0;
      }
    }
    if ((start + 0x0001ffff|0) < len) {
      if ((offset = start + 0x0003ffff|0) < len) {
        start = start + ((array[offset] < sValue) << 18) | 0;
      }
      if ((offset = start + 0x0001ffff|0) < len) {
        start = start + ((array[offset] < sValue) << 17) | 0;
      }
    }
    if ((offset = start + 0x0000ffff|0) < len) {
      start = start + ((array[offset] < sValue) << 16) | 0;
    }
    if ((offset = start + 0x00007fff|0) < len) {
      start = start + ((array[offset] < sValue) << 15) | 0;
    }
  }
  if ((start + 0x0000007f|0) < len) {
    if ((start + 0x000007ff|0) < len) {
      if ((start + 0x00001fff|0) < len) {
        if ((offset = start + 0x00003fff|0) < len) {
          start = start + ((array[offset] < sValue) << 14) | 0;
        }
        if ((offset = start + 0x00001fff|0) < len) {
          start = start + ((array[offset] < sValue) << 13) | 0;
        }
      }
      if ((offset = start + 0x00000fff|0) < len) {
        start = start + ((array[offset] < sValue) << 12) | 0;
      }
      if ((offset = start + 0x000007ff|0) < len) {
        start = start + ((array[offset] < sValue) << 11) | 0;
      }
    }
    if ((start + 0x000001ff|0) < len) {
      if ((offset = start + 0x000003ff|0) < len) {
        start = start + ((array[offset] < sValue) << 10) | 0;
      }
      if ((offset = start + 0x000001ff|0) < len) {
        start = start + ((array[offset] < sValue) << 9) | 0;
      }
    }
    if ((offset = start + 0x000000ff|0) < len) {
      start = start + ((array[offset] < sValue) << 8) | 0;
    }
    if ((offset = start + 0x0000007f|0) < len) {
      start = start + ((array[offset] < sValue) << 7) | 0;
    }
  }
  if ((start + 0x00000007|0) < len) {
    if ((start + 0x0000001f|0) < len) {
      if ((offset = start + 0x0000003f|0) < len) {
        start = start + ((array[offset] < sValue) << 6) | 0;
      }
      if ((offset = start + 0x0000001f|0) < len) {
        start = start + ((array[offset] < sValue) << 5) | 0;
      }
    }
    if ((offset = start + 0x0000000f|0) < len) {
      start = start + ((array[offset] < sValue) << 4) | 0;
    }
    if ((offset = start + 0x00000007|0) < len) {
      start = start + ((array[offset] < sValue) << 3) | 0;
    }
  }

  offset = start + 0x00000003|0;
  nCB = -(offset < len|0) | 0;
  start = start + (((array[offset & nCB] < sValue) << 2) & nCB) | 0;

  offset = start + 0x00000001|0;
  nCB = -(offset < len|0) | 0;
  start = start + (((array[offset & nCB] < sValue) << 1) & nCB) | 0;

  offset = start;
  nCB = -(offset < len|0) | 0;
  start = start + ((array[offset & nCB] < sValue) & nCB) | 0;

  if (array[start|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://dev59.com/EGEh5IYBdhLWcg3wMA_M#44981570
    return -1 - start |0;
  }
  
  return start |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>

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

- Jack G

2

我想指出的是，我的版本被指定为对于空数组返回array.length。如果你喜欢，你可以只返回lo，而不需要额外（昂贵）的比较来判断 !pred(array[i]) && pred(array[1 + i])。你代码中的 hi + lo 项可能会溢出，这可以通过惯用语法 lo + ((hi - lo) >> 1) 来避免。我认为 if … else 比 continue + 标签更易读。此外，我的版本支持任意比较函数符，可以比较数据的部分内容，等等。 ;) - joki

@Joki 是的，你说得对，如果在一个空数组（[]）中搜索 undefined，那么它将返回 0 而不是 -1。然而，我怀疑很少有人（如果有的话）使用 undefined 来存储一个值。因此，我怀疑为了进行额外的检查所需的额外开销根本不会被使用。 - Jack G

2

这正是为什么二分查找比线性查找表现更好的原因——前者只进行对数次比较，而后者则需要进行更多比较，如果比较代价高昂，这将产生很大的差异。在搜索算法中固定比较会使其变得不太灵活，而不改变渐进复杂度，因此在大量数据上的预期加速效果要小得多。 - joki

干得好！只是想指出一个微妙的“错误”（或者也许更好地称之为“意外行为”）：如果未找到该值，则函数应返回“大于该值的元素的索引”，但是如果该值高于最大值，则该值在我看来是错误的。例如，goodBinarySearch([1], 0) 返回 -1（正确），但 goodBinarySearch([1], 2) 也返回 -1，这与前一个结果无法区分（实际上是不同的）。 - marco6

顺便说一下，既然我们正在讨论二分查找和对数算法……这个算法对位进行了“线性”扫描……那么我们能不能在那里也应用二分查找呢？是的！所以我们可以再深入一点。=>https://jsben.ch/KKa4A。有趣的部分是（通常情况下优化都是如此），它不总是更快（即如果您只有大小==2 ^ 32-1，则会执行更多计算（由于数据集非常大，这实际上并不重要...此外，浏览器将内存限制为<2GB，因此您可能无法在数组中拥有2 ^ 32个数字...） - marco6

显示剩余4条评论

12

这里是二分查找函数，您可以进行检查。

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

- Ashutosh Jha

5

我做了一些不同的事情。看看吧。

function binarySearch(arr, n) {
  let min = 0;
  let max = arr.length - 1;
  let mid;
  while (min <= max) {
    mid = (min + max) >>> 1;
    if (arr[mid] === n) {
      return mid;
    } else if (arr[mid] < n) {
      min = mid + 1;
    } else {
      max = mid - 1;
    }
  }

  return -1;
}

binarySearch([1,2,3,5,56], 2);

- Eduard

1

这个答案明显更好。如果对这段代码和选定的答案进行速度分析，我猜测在大型数组上会快100倍。 - Luke Dupin

2

一个类似的问题是查找与搜索X最接近的元素，如果没有完全匹配的话。为了解决这个问题，我们改进了@Alexander Ryzhov的答案，使其始终返回“插入点”=最小的那些大于或等于X的元素的索引。一旦我们得到结果索引I，我们检查在I处的元素（可能是X或大于X），以及I-1处的元素（较小的元素），并选择其中距离X最近的一个。不要忘记处理边缘情况！

function binarySearch(a, compare) {
    let le = 0,
        ri = a.length - 1;

    while (le <= ri) {
        let mid = (le + ri) >> 1,
            cmp = compare(a[mid]);

        if (cmp > 0) {
            le = mid + 1;
        } else if (cmp < 0) {
            ri = mid - 1;
        } else {
            return mid;
        }
    }

    return le;
}


function binaryClosest(a, compare) {
    let i = binarySearch(a, compare);

    if (i === 0)
        return a[0];

    if (i === a.length)
        return a[i - 1];

    let d1 = -compare(a[i]),
        d2 = compare(a[i - 1]);

    return d1 < d2 ? a[i] : a[i - 1];
}


//

input = [-3, -2, -1, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3]
findX = x => binaryClosest(input, item => x - item)

test = (exp, arg) => {
    let x = findX(arg)
    console.log(exp === x ? 'ok' : 'FAIL', arg, exp, x)
};

test(-3, -99)
test(+3, +99)

test(0, +0.3)
test(0, 0)
test(0, -0.3)

test(-1, -1.3)
test(+1, +1.3)

test(2, 2.2)
test(2, 2.3)
test(2, 2.5)
test(3, 2.6)

- georg

你怎么知道 a[i + 1] 不是更接近的呢？我们拿 [1, 10, 15] 和 9 举例，难道不应该从 10 到 1 再返回 1 吗？我错在哪里了？ - Jonas Wilms

@JonasWilms：尽管有return le，但是这个bsearch实际上返回的是正确的边界，因此保证了a[i - 1] < X <= a[i]。在你的例子中，bsearch进行了2次移动：L=0,R=2--向左移动-L=0,R=0--向右移动-L=1,R=0--错误，返回1。请注意，这是索引1，而不是值“1”！ - georg

2

如果有人需要答案，我会发帖回复。

递归和非递归方式
直接附上注释

递归方式

/**
 * Binary Search - With recursive
 * @param arr - Input Array
 * @param searchElement - Element to search
 * @param left - Left index
 * @param right - Right index
 */
function binarySearch(arr, searchElement, left, right) {

  let mid = Math.floor((left + (right + 1)) / 2); // using floor as we may get floating numbers

  if (left <= right) { // If it is not the last element, process further, else return -1
    if (arr[mid] === searchElement) { // element found at mid
      return mid; // no need to process further
    } else if (searchElement < arr[mid]) { // element might be in first half
      right = mid - 1; // right is mid - 1 because we know that mid is not correct element
    } else { // element might be in second half
      left = mid + 1; // left is mid + 1 because we know that mid is not correct element
    }
    return this.binarySearch(arr, searchElement, left, right); // recursive
  }

  return -1; // element not found
}


// Invoking
console.log(binarySearch([1,2,3,4,5], 2, 0, 4));

非递归方法

/**
 * Binary Search - Without using recursive
 * @param arr - Input Array
 * @param searchElement - Element to search
 */
function binarySearch(arr, searchElement) {

  let left = 0,
    right = arr.length - 1;

  while (left <= right) { // Process until it is last element

    let mid = Math.floor((left + (right + 1)) / 2); // using floor as we may get floating numbers

    if (arr[mid] === searchElement) { // element found at mid
      return mid; // no need to process further
    }
    if (searchElement < arr[mid]) { // element might be in first half
      right = mid - 1; // right is mid - 1 because we know that mid is not correct element
    } else { // element might be in second half
      left = mid + 1; // left is mid + 1 because we know that mid is not correct element
    }
  }

  return -1; // element not found
}

// Invoking
console.log(binarySearch([1, 2, 3, 4, 5], 2));

- Manoj Reddy Mettu

1

这是我的解决方案！

// perform a binarysearch to find the position in the array
function binarySearch(searchElement, searchArray) {
    'use strict';

    var stop = searchArray.length;
    var last, p = 0,
        delta = 0;

    do {
        last = p;

        if (searchArray[p] > searchElement) {
            stop = p + 1;
            p -= delta;
        } else if (searchArray[p] === searchElement) {
            // FOUND A MATCH!
            return p;
        }

        delta = Math.floor((stop - p) / 2);
        p += delta; //if delta = 0, p is not modified and loop exits

    }while (last !== p);

    return -1; //nothing found

};

- fstasi

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Alexander Ryzhov · Accepted Answer

如果未找到该元素，则编写搜索函数以返回负值，指示新元素的插入点是非常有用的。此外，在二分查找中使用递归是过度和不必要的。最后，通过将比较器函数作为参数提供，使搜索算法成为通用算法是一种好的做法。下面是实现。

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

这段代码连同注释和单元测试的链接在这里。