Javascript 中的二进制搜索

我正在尝试用 JavaScript 实现一个二进制搜索算法。事情看起来还不错，但我的 return 语句似乎返回了未定义的内容。有人能告诉我这里出了什么问题吗？

小提琴: http://jsfiddle.net/2mBdL/

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);
125540 次浏览
小开
最佳答案

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

看 工作小提琴

小开

这就是我的解决办法！

// 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


};
小开

编写搜索函数时，如果找不到新元素，则返回一个负值，指示新元素的插入点，这种方法非常有用。此外，在二进制搜索中使用递归是过度和不必要的。最后，通过提供一个比较器函数作为参数，使搜索算法具有通用性，是一个很好的实践。下面是实现。

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

这段代码包含注释和一个单元测试 给你。

小开

假设有一个排序的数组，下面是一个递归二进制搜索:

function binSearch(needle, arr) {
length = arr.length;
while(length > 1) {
midpoint = Math.floor(length/2);
return (needle > arr[midpoint-1]) ?
binSearch(needle, arr.splice(midpoint, length)) :
binSearch(needle, arr.splice(0, midpoint));
}
return needle === arr[0] ? arr[0] : -1;
}
小开

您还应该检查“ value not found”边缘情况，并将其作为您的第一个基本条件，然后进行成功的搜索。因此，在遍历数组时，不需要检查数组长度是否 > 1。最后，既然不返回数组，为什么不使用 Array.Prototype.slice 方法呢？

var binarySearch = function(arr, val) {
var half = Math.floor(arr.length / 2);


if (arr.length === 0) {
return -1;
}
else if (arr[half] === val) {
console.log("val: ", val, "arr[half]: ", arr[half]);
return val;
}
else if (val > arr[half]) {
console.log("val: ", val, "arr[half]: ", arr[half]);
return binarySearch(arr.slice(half, arr.length), val);
}
else {
console.log("val: ", val, "arr[half]: ", arr[half]);
return binarySearch(arr.slice(0, half), val);
}
}




var arr = [1, 5, 20, 58, 76, 8, 19, 41].sort(function(a, b) { return a - b });


console.log("Sorted array: " + arr);
console.log(binarySearch(arr, 76));
console.log(binarySearch(arr, 19));
console.log(binarySearch(arr, 0));
小开

我想添加我的 SearchArray二进制搜索函数，连同工具实用函数 insertSortedArray和 removeSortedArray到答案列表中，因为我认为它是干净的，它是全球性的使用，我认为它是相当的速度最佳。

小开

下午好, 我知道这篇文章开始于一段时间以前，但我认为我可能会有助于讨论。

function binarySearch(array, target, max, min) {


//Find the Midpoint between forced max and minimum domain of the array
var mid = ((max - min) >> 1) + min;
//alert("Midpoint Number" + mid);
console.log(mid);
console.log(array[mid], "target: " + target);


if (array[mid] === target) {
//Target Value found
console.log('match', array[mid], target);
//alert('match', array[mid], target);
return mid;
}
else if (mid === 0)
{
//All Value have been checked, and none are the target value, return sentinel value
return -1;
}
else if (array[mid] > target)
{
//Value at Midpoint is greater than target Value, set new maximum to current midpoint
max = mid;
console.log('mid lower', array[mid], target);
//alert('mid lower', array[mid], target);
//Call binarySearch with new search domain
return binarySearch(array, target, max, min);
}


else if (array[mid] < target)
{
// Value at Midpoint is less than the target Value, set new minimum to current midpoint
min = mid;
console.log('mid higher', array[mid], target);
//alert('mid higher', array[mid], target);


//Call binarySearch with new search domain
return binarySearch(array, target, max, min);
}

我确信这里还有改进的余地，但是这个方法可以避免执行数组的深度拷贝(在处理大型数据集时这可能是一个代价高昂的操作) ，同时它不会以任何方式修改数组。

希望能帮上忙！ 谢谢, 杰里米

小开 
function binarySearch(a = [], x) {
let length = a.length;
if (length === 0) {
return false;
} else {
let m = Math.floor(length/2);
let y = a[m];
if (x === y) {
return true;
} else if (x < y) {
return binarySearch(a.slice(0, m), x);
} else {
return binarySearch(a.slice(m + 1), x);
}
}
}
小开

下面是一个 函数式程序设计样式的 ES6函数，如果没有提供默认的比较函数，则使用该函数: 如果所查找的值是数字类型，则假定为数值比较，否则为字符串比较。

function binarySearch(arr, val, compFunc =
(a, b) => typeof val == 'number' ? a-b : a.localeCompare(b), i=0, j=arr.length) {
return i >= j ? i
: ( mid =>
( cmp =>
cmp < 0 ? binarySearch(arr, val, compFunc, i, mid)
: cmp > 0 ? binarySearch(arr, val, compFunc, mid+1, j)
: mid
) (compFunc(val, arr[mid]))
) (i + j >> 1);
}


///////// Tests ///////////////////


function check(arr, val, compFunc) {
var fmt = JSON.stringify;
var result = binarySearch(arr, val); // default compFunc is assumed
console.log(`binarySearch(${fmt(arr)}, ${fmt(val)}) == ${fmt(result)}`);
if (result > arr.length || result < 0 || !arr.length && result
|| result < arr.length && compFunc(val, arr[result]) > 0
|| result > 0 && compFunc(val, arr[result-1]) < 0) throw "Unexpected result!!!"
}


// Tests with numeric data:
for (var val = 0; val < 12; val++)
check([1, 2, 4, 6, 9, 9, 10], val, (a,b) => a-b);
// Test with empty array:
check([], 12, (a,b) => a-b);
// Test with string data:
check(['abc', 'deaf', 'def', 'g'], 'dead', (a, b) => a.localeCompare(b));

小开

对于这个问题有很多可行的解决方案，但是都是在找到匹配后提前返回的。虽然这可能对性能有一个小的积极影响，但是由于二进制搜索的对数性质，这是可以忽略不计的，并且如果比较函数的计算开销很大，实际上可能会损害性能。

更重要的是，它阻止了二进制搜索算法的一个非常有用的应用: 查找一系列匹配元素，也称为查找 低一点或 上界。

下面的实现返回一个索引 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()ed 的，则该函数返回 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);
}

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

小开

这里是二进制搜索函数，你可以检查一下

   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 ;
}
小开

你想要速度? 看看这个。

实现正确的二进制搜索(无需修改数组、制作数组的浅拷贝或其他荒谬之处)在 O (k * log < sub > 2 (n))附近具有平均复杂度(其中 k 是常数，表示不必要的开销)。假设您有一个包含1024个元素的数组，在本例中常量 k 为1。使用线性搜索，平均复杂度为 O (k * n/2) = O (1 * 1024/2) = O (512)。如果使用二进制搜索，则复杂度为 O (k * log < sub > 2 (n)) = O (1 * log < sub > 2 (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 "+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://stackoverflow.com/a/44981570/5601591
return -1 - start |0;
}
return start |0;
}

上述函数的返回值如下。

  • 如果找到该值，则返回该值的索引。
  • 如果没有找到该值，那么它将返回 -1 - nearestIndex，其中 nearestIndex 是找到的最接近的索引数 < = index，最大值为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://stackoverflow.com/a/44981570/5601591
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://stackoverflow.com/a/44981570/5601591
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://stackoverflow.com/a/44981570/5601591
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://stackoverflow.com/a/44981570/5601591
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>

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

小开 

function binarySearch(arr, num, l, r){
if( arr instanceof Array ){
  	

l = isNaN(l) ? 0 : l;
r = isNaN(r) ? arr.length - 1: r;
let mid = l + 1 + Math.round((r - l)/2 - 1);
console.log(l, r, mid, arr[mid]);
    

if( num == arr[mid] ){
console.log("found");
return mid;
}
    

if( typeof arr[mid] == "undefined" || l == r ){
console.log("not found"); return -1;
}
    

if( num < arr[mid] ){
console.log("take left");
return binarySearch(arr, num, l, r - mid);
}
    

console.log("take right");
return binarySearch(arr, num, mid, r);
    

}
}


console.log( binarySearch([0, 0, 1 ,1, 2, 3, 5, 6, 11], 2) );

小开

假设数组已经排序(编写自己的排序算法或者只使用内置方法)

function bSearch(array,item){
var start = 0,
end = item.length - 1;
var middle = Math.floor((end+start)/2);
while(array[middle] !== item && start < end){
if(item < array[middle]){
end = middle-1;
}
else if(item > array[middle]){
start = middle+1;
}
middle = Math.floor((end+start)/2);


}
if(array[item]!== middle){
console.log('notFoundMate);
return -1;
}
else {
console.log('FoundMate);
return middle;
}
}
小开

要使用它，只需按原样复制粘贴，并使用本地变量来提高速度。并修改搜索值，比如在子对象或数组中搜索:

if (array[mid][0] < value[0]) low = mid + 1;
if (array[mid].val < value.val) low = mid + 1;

为了获得更快的结果，可以使用数组或并行数组的数组，将搜索到的数组复制到局部变量。非局部变量或者每次你做对象的时候，它会减慢速度。

最快的版本是这样的:

let array=[3,4,5,6]
let value=5; //searched value
let mid, low = 0,high = array.length;
while (low < high) {
mid = low + high >>> 1; // fast divide by 2 and round down
if (array[mid] < value) low = mid + 1;
else high = mid;
}
//if (array[mid] != value) mid=-1;// this might not be required if you look for place to insert new value
mid;// contains the found value position or if not found one before where it would be if it was found

二进制搜索的工作原理如下:

|           .           |     // find middle
//option 1:
|           .     v     |     // if value on right, middle is top
|     .     |     // so then it is like this
//option 2:
|     v     .           |     // if value on left, middle is bottom
|     .     |                 // so then it is like this
//more loops of option 2 until not found
|  .  |                       // next time it will be like this
|. |                          // next time it will be like this
.                             // next time it will be like this

如果没有找到，这个实现就会到底部。 它总是可以被发现或者不被发现。 它返回下面的索引或等于搜索值。 所以你需要检查它是否等于。验证该值是否存在，或者它只是下面的一个结果。如果你正在寻找一个地方插入客栈顺序只是放在那个地方，没有必要检查如果等于

小开

二进制搜索(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);
}
小开

我认为下面的选项可以简单地在 JS 中实现二进制搜索。

arr = [1,2,3,4,5];
searchTerm=2;
function binarySearchInJS(start,end)
{
isFound=false;
if(end > start)
{
//console.log(start+"\t"+end)
mid =  (end+start)/2;


mid = Math.floor(mid)


if(searchTerm==arr[mid])
{
isFound = true;
}
else
{


if(searchTerm < arr[mid])
{
binarySearchInJS(start,mid);
}
if(searchTerm > arr[mid])
{
binarySearchInJS(mid+1,end);
}
}
}


if(isFound)
{
return "Success";
}
else{
return "Not Found";
}
}
小开

全功能 binarySearch:

  • 负值表示插入点
  • 允许搜索第一个和最后一个索引
  • 开始索引，独占结束索引
  • 自定义比较功能

(此代码和单元测试 给你)

function defaultCompare(o1, o2) {
if (o1 < o2) {
return -1;
}
if (o1 > o2) {
return 1;
}
return 0;
}


/**
* @param array sorted array with compare func
* @param item search item
* @param start (optional) start index
* @param end (optional) exclusive end index
* @param compare (optional) custom compare func
* @param bound (optional) (-1) first index; (1) last index; (0) doesn't matter
*/
function binarySearch(array, item, start, end, compare, bound) {
if (!compare) {
compare = defaultCompare;
}
let from = start == null ? 0 : start;
let to = (end == null ? array.length : end) - 1;
let found = -1;
while (from <= to) {
const middle = (from + to) >>> 1;
const compareResult = compare(array[middle], item);
if (compareResult < 0) {
from = middle + 1;
}
else if (compareResult > 0) {
to = middle - 1;
}
else if (!bound) {
return middle;
}
else if (bound < 0) {
// First occurrence:
found = middle;
to = middle - 1;
}
else {
// Last occurrence:
found = middle;
from = middle + 1;
}
}
return found >= 0 ? found : -from - 1;
}
小开

这个问题的一个变体是找到一个最接近搜索 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)

小开

递归地 将搜索范围分成两半，直到达到合适的值或超出搜索范围:

const binarySearch = (arr, item, [low=0, high=arr.length-1]=[]) => {
const mid = Math.floor((low + high)/2)


if (low > high) return -1 // is overshooting the range?
if (arr[mid] === item) return mid // is item found?


return binarySearch(arr, item, [
item > arr[mid] ? mid+1 : low,
item < arr[mid] ? mid-1 : high
])
}

让我们测试一下:

// positive
console.log(binarySearch([2, 6, 9, 14, 21],  9)) // => 2
console.log(binarySearch([2, 6, 9, 14, 21], 21)) // => 4
console.log(binarySearch([2, 6, 9, 14, 21],  2)) // => 0


// negative
console.log(binarySearch([2, 6, 9, 14, 21],  0)) // => -1
console.log(binarySearch([2, 6, 9, 14, 21], -4)) // => -1
console.log(binarySearch([2, 6, 9, 14, 21], 40)) // => -1
小开

一个递归二进制搜索函数，它将返回正在搜索的元素的 index:

function binarySearch(arr, target, idx=0){
let full_len = arr.length;
if(full_len === 0){
return null;
}
let mid = Math.floor(full_len / 2);
if(arr[mid] === target){
return `INDEX of ${target} is: ${idx+mid}`;
}else if(target > arr[mid]){
let right = arr.slice(mid + 1, full_len);
idx += (full_len - right.length);
return binarySearch(right, target, idx);
}else if(target < arr[mid]){
let left = arr.slice(0, mid);
return binarySearch(left, target, idx);
}
}


//Testing:


var arr = [1, 27, 34, 42, 58, 69, 71, 85, 96, 151];
console.log(binarySearch(arr, 1)); //=> 0
console.log(binarySearch(arr, 27)); //=> 1
console.log(binarySearch(arr, 34)); //=> 2
console.log(binarySearch(arr, 42)); //=> 3
console.log(binarySearch(arr, 58)); //=> 4
console.log(binarySearch(arr, 69)); //=> 5
console.log(binarySearch(arr, 71)); //=> 6
console.log(binarySearch(arr, 85)); //=> 7
console.log(binarySearch(arr, 96)); //=> 8
console.log(binarySearch(arr, 151)); //=> 9
arr = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100];
console.log(binarySearch(arr, 10)); //=> 0
console.log(binarySearch(arr, 20)); //=> 1
console.log(binarySearch(arr, 30)); //=> 2
console.log(binarySearch(arr, 40)); //=> 3
console.log(binarySearch(arr, 50)); //=> 4
console.log(binarySearch(arr, 60)); //=> 5
console.log(binarySearch(arr, 70)); //=> 6
console.log(binarySearch(arr, 80)); //=> 7
console.log(binarySearch(arr, 90)); //=> 8
console.log(binarySearch(arr, 100)); //=> 9


var bigArr = [];
for(var i = 1; i <= 1000000; i++){
bigArr.push(i);
}
console.log(binarySearch(bigArr, 5342)) //=> 5341
console.log(binarySearch(bigArr, 254369)) //=> 254368
console.log(binarySearch(bigArr, 2000000)) //=> null
console.log(binarySearch(bigArr, -1)) //=> null
小开

如果有人需要，可以发布答案

  1. 递归和非递归方式
  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));

小开

这里有很多过于复杂的答案！如果找到了该值，则需要返回索引; 否则，如果该值在数组中，则返回该值所在位置的索引的负值。你也希望它足够通用，除了处理数字之外还能处理语言表达式:

function BinarySearch(array, value) {
let high = array.length - 1;
let low = 0;


if (value < array[low])
return -1;
if (value > array[high])
return -(high + 1);


while (high >= low) {
var mid = (high + low) >> 1;


if (value === array[mid])
return mid;
else if (value < array[mid])
high = mid - 1;
else
low = mid + 1;
}


return -(mid + 1);
}


var c = ['alpha','apple','beta','delta','gamma','zebra'];
console.log(BinarySearch(c,'delta')); // return 3
console.log(BinarySearch(c,'beet')); // return -2
var a = [1,2,3,4,6,7,8,9,10];
var b = [1,2,3,4,5,6,7,8,9,10];
console.log(BinarySearch(a,5)); // return -4
console.log(BinarySearch(a,11)); // return -9
console.log(BinarySearch(b,5)); // return 4
console.log(BinarySearch(b,0)); // return -1

或者，如果只想在找到时返回 true，否则返回 false:

function BinarySearch(array, value) {
let high = array.length - 1;
let low = 0;


if (value < array[low] || value > array[high])
return false;


while (high >= low) {
let mid = (high + low) >> 1;


if (value === array[mid])
return true;
else if (value < array[mid])
high = mid - 1;
else
low = mid + 1;
}


return false;
}
小开

开始了。

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


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


function binarySearch(arr,value){
if(arr.length === 0) return -1;
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 ;
}
console.log(binarySearch(a,1005))

这是工作小提琴 -https://jsfiddle.net/avadhutthorat/6Lq1r582/

小开

有点不一样，看看

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);
小开

没有突变和递归

let A = [ ...Array(100).keys() ].map((x) => Math.floor(Math.random() * 1000)).sort((a,b) => a-b)
const binarySearch = (A, a, b, k) => {
const m = Math.floor((b + a)/ 2);
console.log(a, m, b, k)
if(A[m] === k) {
return m;
}


if(A[a] <= k && k <= A[m]) {
return binarySearch(A, a,   m, k)
}


if(A[m] <  k && k <= A[b]) {
return binarySearch(A, m+1, b, k)
}


return -1;
}
console.log(`key ${A[30]}`);
rez = binarySearch(A, 0, 100, A[30])
console.log(`rez is ${rez} and index of ${A[30]} is ${A.indexOf(A[30])}`);


rez = binarySearch(A, 0, 100, 666)
console.log(`rez is ${rez} and index of ${666} is ${A.indexOf(666)}`);

小开

Zig的 二进制搜索端口:

  • 使用 <而不是 <=，因此少了一个比较
  • 上面允许在 right中使用无符号整型-用于类似 zig 或生锈的语言
  • 计算中间没有溢出 mid-为语言像之字或生锈
const binarySearch = (key, items, compareFn) => {
let left = 0;
let right = items.length;
while (left < right) {
const mid = left + Math.floor((right - left) / 2);
const cmp = compareFn(key, items[mid]);
if (cmp === 0) return mid;
if (cmp < 0) right = mid;
else left = mid + 1;


// happens when right = items.length - 1 and key = 2 and items = [3]
if (right < 0) throw new Error("right is < 0");
}
return -1;
};


const compareFn = (a, b) => a - b;
console.log(binarySearch(33, new Int16Array([1, 3, 4, 2, 33, 20, 10, 12, 34]).sort(), compareFn));
console.log(binarySearch(2, new Int16Array([3]).sort(), compareFn));
小开 

const SearchArray =(Listarr, Key)=>{
  

const midvalues = Math.floor(Listarr.length/2)
 

if(Key===Listarr[midvalues]) return true
  

else if(Listarr[midvalues]<=Key && midvalues>0 )
return SearchArray(Listarr.slice(midvalues,Listarr.length), Key)
  

else if(Listarr[midvalues]>=Key && midvalues>0 )
return SearchArray(Listarr.slice(0, midvalues) , Key)
else
return "No record found"
  

  

}
const arr = [11,24,26,37,40,43,56,75,87];


console.log(SearchArray(arr, 75))
console.log(SearchArray(arr, 87))
console.log(SearchArray(arr, 11))
console.log(SearchArray(arr, 26))


提交答案