Binary Search in Javascript

Question

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 me what's wrong here?

Fiddle: 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);

To return the recursing states, you need `return binarySearch(...)` in each case. — cmbuckley, Mar 27 '14 at 20:01
Splice modifies the original array, see [W3Schools](http://www.w3schools.com/jsref/jsref_splice.asp); this includes it being passed by reference. A good point to start off is http://www.nczonline.net/blog/2009/06/09/computer-science-in-javascript-binary-search-tree-part-1/ — Sunny Patel, Mar 27 '14 at 20:02
It's marked as being unlikely to help future visitors, as it's only a minor error. — cmbuckley, Mar 27 '14 at 20:20
Why are you returning the value that matches the target? That makes the whole search redundant! You should return the index — gb96, Nov 11 '15 at 23:31

score 120 · Answer 1 · edited Jan 13 '23 at 05:43

120

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

This code with comments and a unit test here.

edited Jan 13 '23 at 05:43

BlobKat

88
1
8

answered Mar 12 '15 at 19:34

Alexander Ryzhov

2,705
3
19
19

2

your algorithm returns `-m -1` but your code comments in jsfiddle refer to a return value of `-n -1`. Possible typo? – Darragh McCarthy Oct 08 '15 at 00:13
easy to read, elegant, and succinct. I also like `>> 1` rather than, `/ 2` – Rafael Jul 13 '16 at 15:42
yea it does not work, you need to take make `m = k` and `n = k` – Apr 21 '17 at 00:26
2

In response to the skeptics, I extended the unit tests to a suite of random tests. All tests pass, all the time. Check out the fiddle http://jsfiddle.net/pkfst550/48/ – Alexander Ryzhov Jun 05 '17 at 23:24
1

`-m - 1` can also be written as `~ m` – Venkata Raju Jul 17 '17 at 09:44
3

Return value of 0 is ambiguous. Is the element at the head of the list, or does it need to be inserted there? – Alex Coventry Aug 07 '18 at 19:00
2

A return value of 0 is not ambiguous, it means explicitly "the element is found at index 0". To signify that "the element should be inserted at index 0", the function would return -1 (which is the **bitwise complement** of 0 - "~x" == "-x-1"). – Kenan E. K. Dec 18 '19 at 13:04
2

@Rafael curious why you like `>> 1`? – Dominic Jan 07 '20 at 08:58
1

@Dominic `x >> 1` shifts 1 bit of `x` to the right. It's basically another way to do `Math.floor(x / 2)`. It's also faster... with an average 1ms gain on 10,000,000 iterations (the numbers may not be the same for every computer). [Read more on MDN](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Right_shift). – deb Apr 11 '21 at 12:23
@VenkataRaju Only if `n` is an integer, which it seems to be – deb Apr 11 '21 at 12:38
@Dominic realistically, the gain is within the margin of error, and only serves to confuse begginers – Mattwmaster58 Nov 23 '21 at 05:15
1

@deb @VenkataRaju I'd caution against trying to be clever with `~n`. The bitwise not operator converts its argument to a 32 bit ***signed*** integer while array indices are allowed the full range of 32 bit ***unsigned*** integers, which means for all the perfectly valid array indices from 2^31 up to 2^32-1, `~n !== -n - 1`. – jw013 May 01 '22 at 03:52

score 48 · Answer 2 · edited Jul 26 '21 at 14:51

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

score 37 · Answer 3 · edited Jun 29 '18 at 17:08

37

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.

edited Jun 29 '18 at 17:08

Luca Kiebel

9,790
7
29
44

answered Jan 31 '17 at 11:26

joki

6,619
2
22
30

1

While this does not exactly answer the original question ( though I am confused as to what the point of the original question is ), I voted up anyway because good information can be difficult to find on SO. One suggestion, as life permits, please provide answers like this to questions with a longer history and more activity. Doing so will make your knowledge and experience more accessible to more people. :-) – Nolo Mar 14 '17 at 08:41
Out of curiosity, why `const mi`? Is it for semantic intent, i.e. `mi` should only be assigned once? Seems `let mi` would suffice otherwise. – Nolo Mar 14 '17 at 08:54
1

@Nolo yes, the `const` is semantic – your reasoning is the wrong way round though ;) of course `let` would work because it's more lenient, but here a strict `const` is sufficient – joki Mar 15 '17 at 09:18
@Nolo thanks for the upvote and your suggestion regarding where to post… I think when I wrote this, the title of this question seemed general enough, but I see what you mean by threads with more activity ;) – joki Mar 15 '17 at 09:21
I see. So would this particular case make a difference in what gets emitted from the jit, i.e. `let` vs `const`? Never tried to build and see what comes out of it, really should start doing that. – Nolo Mar 15 '17 at 22:41
1

@Nolo I wouldn't expect it to make a difference in this simple case where the compiler can prove that the variable is never reassigned. I still think it's a good habit to get into ;) – joki Mar 17 '17 at 06:29
1

What's the advantage of `lo + ((hi - lo) >> 1` vs `(hi + lo) >> 1`? – Dominic Aug 09 '20 at 10:59
1

@dominic Well spotted and very good question! `(hi + lo)` overflows as soon as there are more elements than half the range of the integral type. This is a well-known problem in these types of calculations, see for example https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html – joki Aug 10 '20 at 05:15
@joki Aha glad I asked thanks for the link! FYI from the article it appears that JS has an unsigned right shift so it could also be `mi = (lo + hi) >>> 1` I think – Dominic Aug 10 '20 at 06:25
@Dominic yeah it could be, in my original version it was `lo + (hi - lo) / 2` because I think this is most readable and generally the best habit to get into. On modern hardware, integer division is equally efficient as shifting, but somebody edited it for »optimisation«. – joki Aug 10 '20 at 07:51
@joki Integer division is definitely *not* as efficient as shifting, in fact the difference is getting more pronounced in later processor generations. What *is* true is that higher-level optimizations (V8, SpiderMonkey, your C++ compiler etc.) will turn division by a constant power-of-2 into the fast shift for you. – D0SBoots Jan 15 '23 at 23:00
@D0SBoots you are right, hardware performance is the wrong argument – shifting *is* in fact much more efficient, but as you point out lower levels like compiler or VM will take care of this. There are two main reasons I consider it irrelevant in this context: firstly, the whole point of binary search is to minimise the number of iterations. – secondly, the performance of the comparison predicate is expected to vastly dominate the computation of the middle index. – joki Jan 16 '23 at 15:07
@joki Yup! However, in this case the bit shift is actually subtly for *correctness* and not speed: The result of `(1 + 2) >> 1` is 1, but the result of `(1 + 2) / 2` is 1.5. Since JS only (observably) has double arithmetic, you need to use integer-coercing operations to possibly avoid subtle bugs. I'd use `((hi + lo) / 2) | 0` to be more obvious about what's going on, but it's a minor preference. (This is also why the integer overflow concern is irrelevant here.) – D0SBoots Jan 16 '23 at 23:49
@D0SBoots you're right again, my brain was apparently in C++ mode when I wrote that comment – the edit history shows that the answer always used the correct `>> 1` instead of the not-so-subtly broken `/ 2`. Concerning overflow, I think the chances of someone using the formula with integer arithmetic are high enough to justify using `lo + ((hi - lo) >> 1)` out of principle ;-) – joki Jan 17 '23 at 23:42

score 27 · Accepted Answer · answered Mar 27 '14 at 20:01

27

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

answered Mar 27 '14 at 20:01

Eliran Malka

15,821
6
77
100

1

Awesome, thanks. And I guess, it's okay to be splicing the original array? – 4m1r Mar 27 '14 at 20:11
1

well, that is up to you. if you want to avoid mutation of the passed array, clone it beforehand (e.g. `var _arr = arr.slice(0)`). here's [a fiddle for that](http://jsfiddle.net/2mBdL/2/). – Eliran Malka Mar 27 '14 at 20:19
18

Why are you returning the value that matches the target? That makes the whole search redundant! You should return the index. – gb96 Nov 11 '15 at 23:31
2

I would suggest editing this answer to use `slice` instead of `splice`. One would not expect a search function to mutate the haystack. I would use `binarySearch(arr.slice(mid), i)` and `binarySearch(arr.slice(0, mid), i)` instead. – porkbrain Aug 12 '19 at 12:46
1

@gb96, @MichaelBausano, i merely updated the OP's code to fix the issue they pointed, the return values and `splice` impureness seems irrelevant to this issue, so i left them as is to not clutter up the answer – Eliran Malka Aug 22 '19 at 10:32

Jack G · Answer 5 · 2022-11-06T17:25:41.610

? .

Binary searches implemented right (without modifying the array, making shallow copies of the array, or other absurdities) have an average complexity around O(k*log₂(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*log₂(n))=O(1*log₂(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 "+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;
}

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 - nearestIndex where 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.

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

To further optimize performance, we can interleave the if-statements and use bitwise manipulations to make the last three checks branchless like so:

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

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

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

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.

I would just like to point out that my version is specified to return `array.length` for an empty array. You can just `return lo` if you prefer !pred(array[i]) && pred(array[1 + i]), no need for an additional (costly) comparison. The `hi + lo` term in your code might overflow which is avoided by the idiom `lo + ((hi - lo) >> 1)`. I consider `if … else` much more readable than `continue` + label ;). And my version supports arbitrary comparison functors which can compare only part of the data, among other things. ;) — joki, Jul 29 '17 at 12:21
A warning about the code above: if called with an empty array, it will access the first element array[0] on the last line which might cause undesirable behaviour… — joki, Jul 29 '17 at 15:31
@Joki yes, you are correct that if you search for `undefined` in an empty array (`[]`), then it will return `0` instead of `-1`. However, I doubt very many people (if any at all) use `undefined` to store a value. So, I doubt the extra overhead required for that additional check would ever be used at all. — Jack G, Aug 04 '17 at 20:56
@joki Arbitrary comparison functions are slow in javascript (unless natively implemented) because every time any function is called, the function's context has to be pushed onto the stack, then popped off the stack once the function has finished executing. This constant pushing/popping every step of the way is rather inefficient. — Jack G, Jul 15 '18 at 00:29
…which is precisely why binary search performs better than linear search – the former only does a logarithmic number of comparisons compared to the latter, which can make a big difference if comparison is costly. Fixing the comparison in your search algorithm makes it much less versatile without changing the asymptotic complexity, so the expected speedup on large amounts of data is much smaller. — joki, Jul 15 '18 at 08:27
@joki Very good point. I cannot find any flaw in your logic. I wish I could loosen myself up about performance like you do. (+1) — Jack G, Jul 29 '18 at 01:26
@joki To amend my plagiarism of your solution, I have revisited, revisited, and redone my entire answer. — Jack G, Oct 28 '18 at 14:53
Great work! Just pointing out a subtle "bug" (or maybe it's better to call it "unexpected behavior"): the function should return "the index of the element greater than the value" if the value is not found, but if the value is higher than the greater one, the value is IMHO wrong. For example `goodBinarySearch([1], 0)` returns `-1` (correct), but `goodBinarySearch([1], 2)` returns `-1`, too which is indistinguishable from the previous result (while actually different). — marco6, Jun 06 '22 at 10:54
BTW, since we are talking about binary-search and logarithmic algorithms... This algorithm does a "linear" scan of the bits... Can we apply a binary search over there, too? YES! So we can take this a little further => https://jsben.ch/KKa4A . The fun part is that (as usual with optimization) it is not "always" faster (i.e. if you have only sizes == 2^32-1, than it will perform more computation (it won't really matter since the dataset is so big.. Moreover, browsers limit memory to < 2GB, so you probably can't have 2^32 numbers in an array...) — marco6, Jun 06 '22 at 11:32

score 12 · Answer 6 · answered Mar 14 '17 at 05:56

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

Eduard · Answer 7 · 2020-10-31T18:58:28.480

5

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

edited Oct 31 '20 at 18:58

answered Oct 29 '20 at 19:28

Eduard

1,768
2
10
14

1

This answer is drastically better. If a speed analysis of this code and the selected answer was made, my guess is a 100x faster on large arrays. – Luke Dupin Dec 10 '20 at 01:57

georg · Answer 8 · 2019-04-06T13:14:54.877

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)

How do you know that `a[i + 1]` is not closer? Let's take `[1, 10, 15]` and `9`, wouldnt it go from `10` to `1` and then return `1` ? What am I missing? — Jonas Wilms, Apr 06 '19 at 12:22
@JonasWilms: despite `return le`, this bsearch actually returns the right bound, so it's guaranteed that `a[i - 1] < X <= a[i]`. In your example, bsearch makes 2 moves: `L=0,R=2` -- move left - `L=0,R=0` -- move right - `L=1,R=0` -- fault,1 returned. Note, this is index 1, not value "1"! — georg, Apr 06 '19 at 12:46

Manoj Reddy Mettu · Answer 9 · 2019-10-30T19:14:07.313

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

score 1 · Answer 10 · answered Nov 18 '14 at 17:22

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

};

score 1 · Answer 11 · answered Aug 06 '19 at 03:50

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

WesleyAC · Answer 12 · 2020-07-06T17:48:58.160

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

Your code is for me the easiest readable - so I voted. But I cannot read -++ easily, IMHO replace it with ~ that inverts all bits - and is equal to -++: n = -1 * (p + 1) = ~p — BitLauncher, Jun 07 '20 at 20:29
Thanks! Readability is the key for writing code. You make a fair point about the '-++' part. I wasn't too happy with it but chose it over some other options. I took your advice and modified. — WesleyAC, Jun 07 '20 at 23:05

score 0 · Answer 13 · answered Oct 10 '16 at 13:31

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

It would be good to simplify the code so that beginners can understand. — Kiran Mohan, Feb 17 '17 at 19:15
I wanted to give a version that builds on ES6 features. What don't you understand about it? — trincot, Feb 17 '17 at 19:43
Ironic. This may be the most elegant solution, but the exhaustive function call overhead and over-extensive branching make this pretty slow, and by far the most memory-inefficient because each inner layer it has to go through creates a lot of new variables. — Jack G, Jul 07 '17 at 16:27

Purkhalo Alex · Answer 14 · 2019-11-06T21:10:39.493

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

Change `if (low > high) return -1` to `if (low > high) return -low-1`, you got a binary search which could return an insertion point for `item` when no found. :) — vivimice, Sep 11 '19 at 05:24

score 0 · Answer 15 · answered Jan 12 '22 at 09:17

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

rofrol · Answer 16 · 2022-03-30T12:40:19.893

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

score 0 · Answer 17 · answered Aug 12 '22 at 14:32

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

score -1 · Answer 18 · answered Apr 04 '15 at 23:10

-1

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

answered Apr 04 '15 at 23:10

Zack

1,615
18
26

Recursive function calling = slow code; all day every day (pretty much no exceptions). – Jack G Jul 07 '17 at 16:31
1

@JackGiffin: Not to mention `splice` (explained [here](/a/45008309/6314667) why it’s bad). Still upvoted for simplicity and didactic quality. – 7vujy0f0hy Jun 29 '18 at 17:04
@7vujy0f0hy Please help me. I fail to see the didatic quality. The usage of the splice goes against instinct in this code snippet because it is used to cut out the unneeded parts, not zone-in on the needed parts of the search array. – Jack G Jul 03 '18 at 23:10
@JackGiffin: Demonstrates the principle without technical clutter. **Clear and concise.** Human-readable. **Minimal code that works.** Memorable. **Sacrifices efficiency for clarity.** Gives the student freedom to improve it for real-life applications. **Show me better – you can’t.** P.S. Your `splice` argument is [“glass is half-empty”](https://en.wikipedia.org/wiki/Is_the_glass_half_empty_or_half_full%3F)-tier. – 7vujy0f0hy Jul 04 '18 at 16:26

score -1 · Answer 19 · answered May 16 '15 at 15:52

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

I like the way your code is presented, but your base case logic is wrong. Try running your implementation by searching for the number '9' and you'll see that your function exceeds the call stack. You need to check whether the array length is equal to 1 rather than 0, and also check whether that one value is equal to 'val', otherwise there are some situations where your function will recurse infinitely. — bean, Jun 22 '15 at 03:02
Why are you returning the value that matches the target? That makes the whole search redundant! You should return the index. — gb96, Nov 11 '15 at 23:32

Jeremy Noel · Answer 20 · 2016-03-07T15:32:49.907

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

Why are you returning the value that matches the target? That makes the whole search redundant! You should return the index. — gb96, Nov 11 '15 at 23:33
Thanks gb96, I edited my actual solution for posting to strip out some situation specific information and apparently was not paying too much attention when touching that piece. Edited per your VERY necessary correction. — Jeremy Noel, Mar 07 '16 at 15:33

Jannic Beck · Answer 21 · 2016-03-06T15:25:58.833

-1

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

edited Mar 06 '16 at 15:25

answered Feb 22 '16 at 16:42

Jannic Beck

2,385
21
30

That slice may be elegant, but it is pretty unnecessary, and thus not very performant under these circumstances. – Jack G Jul 07 '17 at 16:31

score -1 · Answer 22 · answered Aug 02 '17 at 09:25

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

Silent errors dig one's own grave (notice how the function only executes `if( arr instanceof Array )`). Sure, at first it seems nice: smaller file size. But, the silent errors slowly coalesce into a venomous snake. One day out of the blue, this metaphorical snake lashes out and strikes you down by making your program not work. But, the worst is yet to come: the metaphorical venom seeps into your veins and makes you terribly ill, preventing you from finding the source of the problem in your code. With your final breaths taken in agony and despair, you now regret all the silent errors you used — Jack G, Nov 27 '18 at 22:14

sg28 · Answer 23 · 2017-08-27T06:30:06.693

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

Shimon Doodkin · Answer 24 · 2018-06-28T08:48:11.153

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

score -1 · Answer 25 · answered Jan 02 '19 at 10:16

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

Nikolay Makhonin · Answer 26 · 2019-03-29T09:28:42.047

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

score -1 · Answer 27 · answered Feb 06 '20 at 06:16

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/

ikrabbe · Answer 28 · 2017-09-04T11:01:22.427

-2

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.

edited Sep 04 '17 at 11:01

answered Jul 31 '15 at 13:13

ikrabbe

1,909
12
25

1

then add it? :P - I'm pretty sure the answer to the question is supposed to be contained here in the answer on SO, no? – Julix Aug 06 '17 at 02:59
its in a github gist. I use this not only for stackoverflow, but as a general solution. Please lookup the code there and decide what to do with it. – ikrabbe Sep 04 '17 at 11:00
So you're saying it may well change, thus link is better solution, as reader will see the most up to date version? – Julix Sep 05 '17 at 07:12
It won't change quite likely because that algorithm is very basic standard and I guess I implemented it in a quite minimal, understandable and fast way. It is jus tmy reference point for a leak I miss in javascript. – ikrabbe Oct 05 '17 at 15:30

Binary Search in Javascript

28 Answers28

Binary Search (ES6)

Bottom-up:

Recursive:

? .

Linked

Related