我正在尝试在JavaScript中实现二进制搜索算法。事情似乎没问题,但我的回复陈述似乎是未定义的回归?谁能说出这里有什么问题?
小提琴: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);
您没有显式返回递归内部调用(即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 {
// ...
您还应检查“未找到值”边缘情况,并将其作为第一个基本条件,然后成功搜索。因此,在递归数组时,您不需要检查数组长度是否> 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));
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);
}
}
}
大家下午好,我理解这篇文章是在不久前开始的,但我认为我可能会为讨论做出贡献。
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);
}
我确信这里有改进的余地,但是这种方法可以防止必须执行数组的深层复制(在处理大型数据集时这可能是一个代价高昂的操作)并且同时它不会修改数组以任何方式。
希望有所帮助!谢谢,杰里米
我在github上有一个实现,比较二进制和线性以及测试页面,如果你仍然有兴趣看到更多的实现here
这是函数式编程风格的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));
我刚刚在代码审查中发现了这个splice
实现,所以我觉得澄清这个实现有多糟糕很重要。
首先,BinarySearch是一种算法,在O(log(n))中,在排序数组中找到一个索引,我们可以插入我们的项目并且仍然有排序数组(我们也可以使用它来查找最接近的项目 - 所以在评论中回答一些问题 - 有一种感觉可以返回一个值 - 它可以与您查询的值不同
在splice
实现中存在重大设计失败 - 搜索算法修改查询数组。想象一下,你有一个数据库,你查询SELECT * FROM data WHERE id=1
,你的一半表被删除。在传递给BinarySearch之前克隆数组不是很有帮助,但我将在下一段解释原因。
所以我们修复这个设计失败并使用一个新的函数slice
,它可以像splice
一样工作,但它不会修改数组(只返回选定的元素)。这个算法还有一个很大的缺陷。对于n=2^m
阵列,我们进行m
测试。首先我们将从slice
n/2
元素返回,下次n/4
,然后n/8
等。如果我们总结一下,它将是n-1
元素。所以我们有O(n)
算法,它和线性搜索一样快,但更复杂(线性搜索更快,因为它的平均成本是n/2
和slice
BinarySearch远离n-1
)。最初的splice
实现更糟糕 - 每个splice
将需要额外的移动元素在表中,所以在最坏的情况下,第一次它将是n
第二n/2
第三n/4
所以最终它将是2 * n - 1
- 这就是为什么克隆数组不是非常有用(克隆是O(n)
所以从来没有克隆你的数组,然后传递给良好的二进制搜索算法)
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;
}
}
我想将searchArray二进制搜索功能与工具实用功能insertSortedArray
和removeSortedArray
一起添加到答案列表中,因为我认为它很干净,它具有全局用途,我认为它非常速度最佳。
以这样的方式编写搜索函数是有用的,即如果找不到该元素,它返回一个负值,表示新元素的插入点。此外,在二进制搜索中使用递归过度且不必要。最后,通过提供比较器函数作为参数,使搜索算法通用是一种很好的做法。以下是实施。
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;
}
此代码带有注释和单元测试here。
要使用它,只需按原样复制粘贴,使用局部变量来提高速度。并修改搜索的值,就像在子对象或数组中搜索一样:
if (array[mid][0] < value[0]) low = mid + 1;
if (array[mid].val < value.val) low = mid + 1;
为了更快的结果,使用数组或数组或并行数组的数组,将搜索到的数组复制到局部变量。非局部变量或每次你做obj.something它减慢。
这是最快的版本是这样的:
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
如果没有找到,这个实现就会到底。它总是可以找到或找不到。它返回下面的索引或等于搜索的值。所以你需要检查它是否等于。验证值是否存在或者只是下面的一个结果。如果你正在寻找一个地方插入客栈订单只是放在那个地方,没有必要检查是否等于
我认为下面的选项很简单,可以在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";
}
}
全功能二进制搜索:
(此代码和单元测试here)
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;
}
让我们考虑优雅的递归示例,尾部调用对大多数提供ES6标准的浏览器都有性能影响:
function binarySearch(arr, item) {
function search(low, high) {
if (low > high) return -1
const mid = Math.floor((low + high)/2)
if (arr[mid] === item) return mid
const nextLow = item > arr[mid] ? mid+1 : low
const nextHigh = item < arr[mid] ? mid-1 : high
return search(nextLow, nextHigh)
}
return search(0, arr.length-1)
}
积极测试:
binarySearch([2, 6, 9, 14, 21], 9) // => 2
binarySearch([2, 6, 9, 14, 21], 21) // => 4
binarySearch([2, 6, 9, 14, 21], 2) // => 0
否定测试:
binarySearch([2, 6, 9, 14, 21], 0) // => -1
binarySearch([2, 6, 9, 14, 21], -4) // => -1
binarySearch([2, 6, 9, 14, 21], 40) // => -1
您不能将二进制搜索用于未排序的数组。你应该[1,4,13,77 ......]而不是[1,2,13,5,17 ......] ......我的坏,你做了排序()
这个问题有许多可行的解决方案,但是一旦找到匹配项,它们都会提前返回。虽然这可能对性能产生很小的积极影响,但由于二进制搜索的对数性质,这可以忽略不计,如果比较函数的计算成本很高,实际上可能会损害性能。
更重要的是,它阻止了二进制搜索算法的非常有用的应用:找到一系列匹配元素,也称为查找下限或上限。
以下实现返回索引0
≤i
≤array.length
,使得给定谓词为false
的array[i - 1]
和true
的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 === hi
暗示!pred(array[hi - 1]) && pred(array[hi])
(期望的后置条件)时,算法终止。
如果数组相对于比较函数sort()
进行compare
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 ;
}
这是我的解决方案!
// 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
};
// bottom-up
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;
}
不同的方法:
// recursive
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);
}
这个问题的一个变体是找到一个最接近搜索X
的元素,如果没有完全匹配的话。
为此,我们调整@Alexander Ryzhov's answer,使其始终返回“插入点”=大于或等于X
的那些元素中最小的索引。
一旦我们得到结果指数I
,我们检查I
(可能是X
或大于X
)和I-1
(更小)的元素并选择两者中最接近的元素。不要忘记处理边缘情况!
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)
实现的二进制搜索(不修改数组,制作数组的副本或其他荒谬)的平均复杂度大约为O(k * log2(n))(其中k是常数,表示不必要的开销)。假设你有一个1024个元素的数组,在这种情况下常数k是1。使用线性搜索,平均复杂度将是O(k * n / 2)= O(1 * 1024/2)= O(512)。使用二进制搜索,您将具有O(k * log2(n))= O(1 * log2(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];
document.write(slowestBS(sArr, 14)); // don't use document.write in production
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
return -1 - start - len |0;
}
return start + len |0;
}
上述功能的返回值如下。
-1 - nearestIndex
,其中nearestIndex是找到的索引,其中最接近的数字<= index并且上限为0。要开始优化,让我们首先删除那个讨厌的内部if-branch。
const sArr = [0,4,5,6,9,13,14,21,27,44];
document.write(compactBS(sArr, 44)); // don't use document.write in production
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
return -1 - start - len |0;
}
return start + len |0;
}
现在,然后,展开它,预先计算它,快速,好,好,就像那样:
const sArr = [0,4,5,6,9,13,14,21,27,44];
document.write(goodBinarySearch(sArr, 5)); // don't use document.write in
// production
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
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 (let x of sArr) // don't use for-of in production
// this statement is esoteric: a traditional for loop is always faster
// than for-of, and even more so faster when you need the index!
document.write(x+" is at "+compFunc(x)+"<br/>"); // don't use document.write
// in production
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
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
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>
您还可以在演示中使用字符串数组(用引号括起来),它应该可以正常工作。要搜索字符串,必须在搜索值周围加上引号。
假设有一个排序数组,这里是一个递归二进制搜索:
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;
}