Binary Search in Javascript
JavascriptBinary SearchJavascript Problem Overview
I'm trying to implement a binary search algorithm in JavaScript. Things seem okay, but my return statements appear to be returning undefined? Can anybody tell what's wrong here?
Fiddle: http://jsfiddle.net/2mBdL/
Thanks.
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);
Javascript Solutions
Solution 1 - Javascript
It's useful to write a search function in such a way that it returns a negative value indicating the insertion point for the new element if the element is not found. Also, using recursion in a binary search is excessive and unnecessary. And finally, it's a good practice to make the search algorithm generic by supplying a comparator function as a parameter. Below is the implementation.
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;
}
This code with comments and a unit test here.
Solution 2 - Javascript
There are many workable solutions to this question, but all of them return early once they have found a match. While this might have a small positive effect on performance, this is negligible due to the logarithmic nature of binary search and can actually hurt performance if the comparison function is expensive to compute.
What is more, it prevents a very useful application of the binary search algorithm: finding a range of matching elements, also known as finding the lower or upper bound.
The following implementation returns an index 0 ≤ i ≤ array.length such that the given predicate is false for array[i - 1] and true for array[i]. If the predicate is false everywhere, array.length is returned.
/**
* 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;
}
Assume for the sake of argument that pred(array[-1]) === false and pred(array[array.length]) === true (although of course the predicate is never evaluated at those points). The loop maintains the invariant !pred(array[lo]) && pred(array[hi]). The algorithm terminates when 1 + lo === hi which implies !pred(array[hi - 1]) && pred(array[hi]), the desired postcondition.
If an array is sort()ed with respect to a comparison function compare, the function returns the smallest insert position of an item when invoked as
binarySearch(array, j => 0 <= compare(item, j));
An insert position is an index at which an item would be found if it existed in the array.
It is easy to implement lower and upper bound for an array in natural ordering as follows.
/**
* 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);
}
Of course, this is most useful when the array can contain several elements that compare identically, for example where elements contain additional data that is not part of the sort criteria.
Solution 3 - Javascript
You're not explicitly returning the recursive inner calls (i.e. return binarySearch()), so the call stack unfolds with no return value. Update your code like so:
// ...
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 {
// ...
See a working fiddle
Solution 4 - Javascript
Binary Search (ES6)
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);
}
Solution 5 - Javascript
헬헼혂 현헮헻혁 혀헽헲헲헱? 헥헲헮헱 혁헵헶혀.
Binary searches implemented right (without modifying the array, making shallow copies of the array, or other absurdities) have an average complexity around O(k*log2(n)) (where k is constant representing needless overhead). Say you have an array of 1024 elements, and the constant k is 1 in this case. With a linear search, the average complexity would be O(k*n/2)=O(1*1024/2)=O(512). With a binary search, you would have a complexity of O(k*log2(n))=O(1*log2(1024))=O(1*10)=O(10). Now, say that you make both the linear search algorithm 25% faster and the binary search algorithm 25% faster. Now, k is 0.75 for both algorithms. The complexity of the linear search decreases to O(384) (a gain of 128 performance points), whereas the binary search decreases to O(7.5) (a gain of only 2.5 performance points). This minimal gain from optimizing the binary search method is because the binary search method is already so fast. Therefore, any sane person should be more inclined to optimize the rest of their program before they try to optimize their binary search algorithm. Despite this clear line of reasoning, I eventually gave into temptations and optimized the binary search function to the absolute limits of JavaScript engineering.
To start off the performance maxima, let us first investigate the initial function I started with. This function may be much slower than the ones shown further down the page (it's still much faster than any other answer posted here), but it should be much less confusing.
const sArr = [0,4,5,6,9,13,14,21,27,44];
const s = sArr[Math.random() * sArr.length | 0];
document.body.innerHTML = s+" is at "+slowestBS(sArr, s);
function slowestBS(array, searchedValue, ARG_start, ARG_len){
// Range of [start, start+len): only start is inclusive. It works
// similarly to "...".substr(start, len).indexOf(sValue)
// `void 0` is shorthand for `undefined`
var start = ARG_start |0;
var len = (ARG_len === void 0 ? (array.length|0)-start : ARG_len) | 0;
len = len - 1 |0;
for (let i=0x80000000; i; i >>>= 1) {
if (len & i) {
const withoutCurBit = len & ~(i-1);
if (array[start + withoutCurBit] > searchedValue) {
len = withoutCurBit - 1 |0;
}
}
}
if (array[start+len] !== searchedValue) {
// remove this if-statement to return the next closest
// element going downwards from the searched-for value
// OR 0 if the value is less than all values in the
// array. https://stackoverflow.com/a/44981570/5601591
return -1 - start - len |0;
}
return start + len |0;
}
The return value of the above function is as follows.
- If the value was found, then it returns the index of the value.
- If the value was not found, then it returns
-1 - nearestIndexwhere the nearestIndex is the index found which is the closest number <= index and capped at 0. - If the array is not sorted within the specified range, then it will return some meaningless number.
To start the optimizations, let us first remove that pesky inner if-branch.
const sArr = [0,4,5,6,9,13,14,21,27,44];
const s = sArr[Math.random() * sArr.length | 0];
document.body.innerHTML = s+" is at "+compactBS(sArr, s);
function compactBS(array, searchedValue, ARG_start, ARG_len){
// `void 0` is shorthand for `undefined`
var start = ARG_start === void 0 ? 0 : ARG_start |0;
var len = (ARG_len === void 0 ? (array.length|0) - start : ARG_len) |0;
len = len - 1 | 0;
for (let i=0x80000000; i; i >>>= 1) {
if (len & i) {
const noCBit = len & ~(i-1);
// noCBits now contains all the bits in len that are
// greater than the present value of i.
len ^= (
(len ^ (noCBit-1)) &
((array[start+noCBit] <= searchedValue |0) - 1 >>>0)
); // works based on the logic that `(x^y)^x === y` is always true
}
}
if (array[start+len] !== searchedValue) {
// remove this if-statement to return the next closest
// element going downwards from the searched-for value
// OR 0 if the value is less than all values in the
// array. https://stackoverflow.com/a/44981570/5601591
return -1 - start - len |0;
}
return start + len |0;
}
And now, then, unroll it, precompute it, make it fast, nice and good, just like that:
const sArr = [0,4,5,6,9,13,14,21,27,44];
const s = sArr[Math.random() * sArr.length | 0];
document.body.innerHTML = s+" is at "+goodBinarySearch(sArr, s);
function goodBinarySearch(array, sValue, ARG_start, ARG_len){
// Range of [start, start+len): only start is inclusive. It works
// similarly to "...".substr(start, len).indexOf(sValue)
// `void 0` is shorthand for `undefined`
var start = (ARG_start === void 0 ? 0 : ARG_start) | 0;
var len = (ARG_len === void 0 ? (array.length|0) - start : ARG_len) |0;
len = len - 1 |0;
if (len & 0x80000000) {
const nCB = len & 0x80000000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x40000000) {
const nCB = len & 0xc0000000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x20000000) {
const nCB = len & 0xe0000000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x10000000) {
const nCB = len & 0xf0000000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x8000000) {
const nCB = len & 0xf8000000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x4000000) {
const nCB = len & 0xfc000000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x2000000) {
const nCB = len & 0xfe000000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x1000000) {
const nCB = len & 0xff000000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x800000) {
const nCB = len & 0xff800000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x400000) {
const nCB = len & 0xffc00000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x200000) {
const nCB = len & 0xffe00000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x100000) {
const nCB = len & 0xfff00000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x80000) {
const nCB = len & 0xfff80000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x40000) {
const nCB = len & 0xfffc0000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x20000) {
const nCB = len & 0xfffe0000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x10000) {
const nCB = len & 0xffff0000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x8000) {
const nCB = len & 0xffff8000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x4000) {
const nCB = len & 0xffffc000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x2000) {
const nCB = len & 0xffffe000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x1000) {
const nCB = len & 0xfffff000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x800) {
const nCB = len & 0xfffff800;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x400) {
const nCB = len & 0xfffffc00;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x200) {
const nCB = len & 0xfffffe00;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x100) {
const nCB = len & 0xffffff00;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x80) {
const nCB = len & 0xffffff80;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x40) {
const nCB = len & 0xffffffc0;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x20) {
const nCB = len & 0xffffffe0;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x10) {
const nCB = len & 0xfffffff0;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x8) {
const nCB = len & 0xfffffff8;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x4) {
const nCB = len & 0xfffffffc;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x2) {
const nCB = len & 0xfffffffe;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x1) {
const nCB = len & 0xffffffff;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (array[start+len|0] !== sValue) {
// remove this if-statement to return the next closest
// element going downwards from the searched-for value
// OR 0 if the value is less than all values in the
// array. https://stackoverflow.com/a/44981570/5601591
return -1 - start - len |0;
}
return start + len |0;
}
But wait... asunder whispers the eve of even greater performance. Likely, you are calling the binary search in a tight loop. In such a case, we can precompute the first value that will actually get processed and skip right to it with a high performance integer index switch statement. HOWEVER, while using this, you must make certain that you never reuse the generated fast function after the length of the array has been modified because then only part of the array will be searched.
const clz32 = Math.clz32 || (function(log, LN2){
return function(x) {
return 31 - log(x >>> 0) / LN2 | 0; // the "| 0" acts like math.floor
};
})(Math.log, Math.LN2);
const sArr = [0,4,5,6,9,13,14,21,27,44];
const compFunc = fastestBS(sArr);
for (var i=0,str="",len=sArr.length|0; i < len; i=i+1|0)
str += sArr[i]+" is at "+compFunc(sArr[i])+"<br/>";
document.body.innerHTML = str; // show the result
function fastestBS(array, ARG_start, ARG_initLen){
// Range of [start, start+len): only start is inclusive. It works
// similarly to "...".substr(start, len).indexOf(sValue)
// `void 0` is shorthand for `undefined`
var start = ARG_start === void 0 ? 0 : ARG_start |0;
var initLen = (ARG_initLen===void 0 ? (array.length|0)-start : ARG_initLen) |0;
initLen = initLen - 1 |0;
const compGoto = clz32(initLen) & 31;
return function(sValue) {
var len = initLen | 0;
switch (compGoto) {
case 0:
if (len & 0x80000000) {
const nCB = len & 0x80000000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
case 1:
if (len & 0x40000000) {
const nCB = len & 0xc0000000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
case 2:
if (len & 0x20000000) {
const nCB = len & 0xe0000000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
case 3:
if (len & 0x10000000) {
const nCB = len & 0xf0000000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
case 4:
if (len & 0x8000000) {
const nCB = len & 0xf8000000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
case 5:
if (len & 0x4000000) {
const nCB = len & 0xfc000000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
case 6:
if (len & 0x2000000) {
const nCB = len & 0xfe000000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
case 7:
if (len & 0x1000000) {
const nCB = len & 0xff000000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
case 8:
if (len & 0x800000) {
const nCB = len & 0xff800000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
case 9:
if (len & 0x400000) {
const nCB = len & 0xffc00000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
case 10:
if (len & 0x200000) {
const nCB = len & 0xffe00000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
case 11:
if (len & 0x100000) {
const nCB = len & 0xfff00000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
case 12:
if (len & 0x80000) {
const nCB = len & 0xfff80000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
case 13:
if (len & 0x40000) {
const nCB = len & 0xfffc0000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
case 14:
if (len & 0x20000) {
const nCB = len & 0xfffe0000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
case 15:
if (len & 0x10000) {
const nCB = len & 0xffff0000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
case 16:
if (len & 0x8000) {
const nCB = len & 0xffff8000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
case 17:
if (len & 0x4000) {
const nCB = len & 0xffffc000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
case 18:
if (len & 0x2000) {
const nCB = len & 0xffffe000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
case 19:
if (len & 0x1000) {
const nCB = len & 0xfffff000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
case 20:
if (len & 0x800) {
const nCB = len & 0xfffff800;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
case 21:
if (len & 0x400) {
const nCB = len & 0xfffffc00;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
case 22:
if (len & 0x200) {
const nCB = len & 0xfffffe00;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
case 23:
if (len & 0x100) {
const nCB = len & 0xffffff00;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
case 24:
if (len & 0x80) {
const nCB = len & 0xffffff80;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
case 25:
if (len & 0x40) {
const nCB = len & 0xffffffc0;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
case 26:
if (len & 0x20) {
const nCB = len & 0xffffffe0;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
case 27:
if (len & 0x10) {
const nCB = len & 0xfffffff0;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
case 28:
if (len & 0x8) {
const nCB = len & 0xfffffff8;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
case 29:
if (len & 0x4) {
const nCB = len & 0xfffffffc;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
case 30:
if (len & 0x2) {
const nCB = len & 0xfffffffe;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
case 31:
if (len & 0x1) {
const nCB = len & 0xffffffff;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
}
if (array[start+len|0] !== sValue) {
// remove this if-statement to return the next closest
// element going downwards from the searched-for value
// OR 0 if the value is less than all values in the
// array. https://stackoverflow.com/a/44981570/5601591
return -1 - start - len |0;
}
return start + len |0;
};
}
Demo:
(function(document){"use strict";
var textarea = document.getElementById('inputbox'),
searchinput = document.getElementById('search'),
searchStart = document.getElementById('start'),
searchedLength = document.getElementById('length'),
resultbox = document.getElementById('result'),
timeoutID = -1;
function doUpdate(){
try {
var txt = textarea.value.replace(/\s*\[|\]\s*/g, '').split(',');
var arr = JSON.parse(textarea.value);
var searchval = JSON.parse(searchinput.value);
var textmtchs = textarea.value.match(/\s*\[|\]\s*/g);
var start = searchStart.value || void 0;
var sub = searchedLength.value || void 0;
txt = refSort(txt, arr);
textarea.value = textmtchs[0] +
txt.join(',') +
textmtchs[textmtchs.length-1];
arr = JSON.parse(textarea.value);
resultbox.value = goodBinarySearch(arr, searchval, start, sub);
} catch(e) {
resultbox.value = 'Error';
}
}
textarea.oninput = searchinput.oninput =
searchStart.oninput = searchedLength.oninput =
textarea.onkeyup = searchinput.onkeyup =
searchStart.onkeyup = searchedLength.onkeyup =
textarea.onchange = searchinput.onchange =
searchStart.onchange = searchedLength.onchange = function(e){
clearTimeout( timeoutID );
timeoutID = setTimeout(doUpdate, e.target === textarea ? 384 : 125);
}
function refSort(targetData, refData) {
var indices = Object.keys(refData);
indices.sort(function(indexA, indexB) {
if (refData[indexA] < refData[indexB]) return -1;
if (refData[indexA] > refData[indexB]) return 1;
return 0;
});
return indices.map(function(i){ return targetData[i] })
}
function goodBinarySearch(array, sValue, ARG_start, ARG_len){
// Range of [start, start+len): only start is inclusive. It works
// similarly to "...".substr(start, len).indexOf(sValue)
// `void 0` is shorthand for `undefined`
var start = (ARG_start === void 0 ? 0 : ARG_start) | 0;
var len = (ARG_len === void 0 ? (array.length|0) - start : ARG_len) |0;
len = len - 1 |0;
if (len & 0x80000000) {
const nCB = len & 0x80000000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x40000000) {
const nCB = len & 0xc0000000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x20000000) {
const nCB = len & 0xe0000000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x10000000) {
const nCB = len & 0xf0000000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x8000000) {
const nCB = len & 0xf8000000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x4000000) {
const nCB = len & 0xfc000000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x2000000) {
const nCB = len & 0xfe000000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x1000000) {
const nCB = len & 0xff000000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x800000) {
const nCB = len & 0xff800000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x400000) {
const nCB = len & 0xffc00000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x200000) {
const nCB = len & 0xffe00000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x100000) {
const nCB = len & 0xfff00000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x80000) {
const nCB = len & 0xfff80000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x40000) {
const nCB = len & 0xfffc0000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x20000) {
const nCB = len & 0xfffe0000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x10000) {
const nCB = len & 0xffff0000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x8000) {
const nCB = len & 0xffff8000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x4000) {
const nCB = len & 0xffffc000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x2000) {
const nCB = len & 0xffffe000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x1000) {
const nCB = len & 0xfffff000;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x800) {
const nCB = len & 0xfffff800;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x400) {
const nCB = len & 0xfffffc00;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x200) {
const nCB = len & 0xfffffe00;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x100) {
const nCB = len & 0xffffff00;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x80) {
const nCB = len & 0xffffff80;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x40) {
const nCB = len & 0xffffffc0;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x20) {
const nCB = len & 0xffffffe0;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x10) {
const nCB = len & 0xfffffff0;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x8) {
const nCB = len & 0xfffffff8;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x4) {
const nCB = len & 0xfffffffc;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x2) {
const nCB = len & 0xfffffffe;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (len & 0x1) {
const nCB = len & 0xffffffff;
len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
}
if (array[start+len|0] !== sValue) {
// remove this if-statement to return the next closest
// element going downwards from the searched-for value
// OR 0 if the value is less than all values in the
// array. https://stackoverflow.com/a/44981570/5601591
return -1 - start - len |0;
}
return start + len |0;
}
})(document);
<h3 style="margin:.125em;width:100%;text-align:center">The Array (Must Be A Valid JSON Array)</h3>
<textarea placeholder="[-24, -12, 0, 0, 9, 16, 18, 64, 80]" type="text" rows=6 style="width:calc(100% - .5em);display:block" id="inputbox">[-24, -12, 0, 0, 9, 16, 18, 64, 80]</textarea>
<table style="table-layout:fixed;font-size:1.2em" width="100%"><tbody>
<tr>
<td colspan="3">Search Value: <input type="text" id="search" value="-12" style="width:8em;text-align:center;float:right" /></td>
<td></td>
<td colspan="3">Resulting Index: <input type="text" id="result" value="1" style="width:8em;text-align:center;float:right" readonly="" />
</tr>
<tr>
<td colspan="3">Start Index: <input type="text" id="start" value="" placeholder="(0)" style="width:8em;text-align:center;float:right" /></td>
<td></td>
<td colspan="3">Searched Length: <input type="text" id="length" value="" placeholder="(array length)" style="width:8em;text-align:center;float:right" />
</tr>
</tbody></table>
You can also use an array of strings (surrounded by quotation marks) in the demo, and it should work just fine. To search for a string, you must put quotes around the search value.
Solution 6 - Javascript
Here is the binary search function , you can check
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 ;
}
Solution 7 - Javascript
Did a bit differently. Take a look
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);
Solution 8 - Javascript
A variation of this problem is finding an element closest to the search X if there's no exact match.
To do that, we adapt @Alexander Ryzhov's answer so that it always returns the "insertion point" = index of the smallest of those elements that are greater than or equal to X.
Once we get the result index I, we check the elements at I (which might be X or greater than X) and I-1 (which is smaller) and choose the closest among the two. Don't forget to handle edge cases!
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)
Solution 9 - Javascript
Posting the answer if in case someone wants
- Recursive and non-recursive way
- With comments straight away
Recursive way
/**
* 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));
Non-Recursive way
/**
* 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));
Solution 10 - Javascript
This is my solution!
// 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
};
Solution 11 - Javascript
A recursive binary-search function that will return the index of the element being searched for:
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
Solution 12 - Javascript
A lot of overly complicated answers here! You want to return the index if the value is found; otherwise return the negative of the index where the value would have been, if it had been in the array. You also want it to be generic enough to handle linguistic expressions in addition to numbers:
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
Or, if you just want to return true if found and false otherwise:
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;
}
Solution 13 - Javascript
Here is an ES6 function in functional programming style, that uses a default compare function if none provided: if the value looked for is of the number type, numeric comparison will be assumed, otherwise string comparison.
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));
Solution 14 - Javascript
Recursively divides the searching range by half until reaching the appropriate value or overshooting the searching range:
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
])
}
Let's test it:
// 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
Solution 15 - Javascript
no mutations and recursive
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)}`);
Solution 16 - Javascript
Port of zig's binarySearch:
- Uses
<instead of<=so one less comparison - Above allows to use unsigned int for
right- for languages like zig or rust - Computes middle without overflowing
mid- for languages like zig or rust
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));
Solution 17 - Javascript
Assuming a sorted array, here's a recursive binary search:
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;
}
Solution 18 - Javascript
You should also check for the "value not found" edge case, and make it your first base condition, followed by a successful search. Consequently you do not need to check for array length > 1 when recursing through the array. Finally, since you don't return the array, why not use the Array.prototype.slice method?
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));
Solution 19 - Javascript
Good afternoon, I understand this post started some time ago, however I thought I could possibly contribute to the discussion.
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);
}
I am sure there is room for refinement here, but this method prevents having to perform a deep copy of the array (which can be a costly action when working with a large data set) and at the same time, it does not modify the array in any way.
Hope that helps! Thanks, Jeremy
Solution 20 - Javascript
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);
}
}
}
Solution 21 - Javascript
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) );
Solution 22 - Javascript
Let's assume the array is sorted (either write ur own sorted algorithm or just use inbuilt methods)
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;
}
}
Solution 23 - Javascript
to use it, just copy paste it as-is, to use local variables for speed. and modify the searched value like if you search in sub objects or arrays:
if (array[mid][0] < value[0]) low = mid + 1;
if (array[mid].val < value.val) low = mid + 1;
for faster results use arrays or arrays of arrays or parallel arrays, copy searched arrays to local variables. nonlocal variables or each time you do obj.something it slows down.
this is the fastest version is like this:
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
binary search works like this:
| . | // 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
this implementation goes to the bottom if not found. it could be found or not found always. it returns the index below or equals to the searched value. so you need to check if it equals. to validate if the value exists or it is just one result below. if you are looking for a place to insert inn order just put at that place, no need to check if equals
Solution 24 - Javascript
I think below option is simple to implement binary search in 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";
}
}
Solution 25 - Javascript
Full featured binarySearch:
- Negative value is indicate the insertion point
- Allow to search first and last index
- start index, exclusive end index
- Custom compare function
(this code and unit test 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;
}
Solution 26 - Javascript
Here we go.
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))
Here is the working fiddle - https://jsfiddle.net/avadhutthorat/6Lq1r582/
Solution 27 - Javascript
I want to add my searchArray binary search function, together with tool utility functions insertSortedArray and removeSortedArray to the list of answers, as I think it's clean, it is of global usage and I think it is quite speed optimal.
Solution 28 - Javascript
You can't use binary search for unsorted array. you should have [1, 4, 13, 77 ...] but not [1, 2, 13, 5, 17 ...] ... my bad, you did sort()