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

Unspotted

also, why is 'a' being modified by arr.splice? – Unspotted

To return the recursing states, you need return binarySearch(...) in each case. – Pushy

Splice modifies the original array, see W3Schools; this includes it being passed by reference. A good point to start off is nczonline.net/blog/2009/06/09/… – Hickey

It's marked as being unlikely to help future visitors, as it's only a minor error. – Pushy

Why are you returning the value that matches the target? That makes the whole search redundant! You should return the index – Fontanel

Answer 1

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

Peacetime

Awesome, thanks. And I guess, it's okay to be splicing the original array? – Unspotted

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. – Peacetime

Why are you returning the value that matches the target? That makes the whole search redundant! You should return the index. – Fontanel

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. – Bigner

@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 – Peacetime

Answer 2

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.

Amine

your algorithm returns -m -1 but your code comments in jsfiddle refer to a return value of -n -1. Possible typo? – Hereon

easy to read, elegant, and succinct. I also like >> 1 rather than, / 2 – Benedictus

yea it does not work, you need to take make m = k and n = k – Strychnic

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 jsfiddle.net/pkfst550/48 – Amine

-m - 1 can also be written as ~ m – Chauvinism

Return value of 0 is ambiguous. Is the element at the head of the list, or does it need to be inserted there? – Keiko

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"). – Paleethnology

@Benedictus curious why you like >> 1? – Sweatbox

@Sweatbox 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. – Vidda

@VenkataRaju Only if n is an integer, which it seems to be – Vidda

@Sweatbox realistically, the gain is within the margin of error, and only serves to confuse begginers – Piotrowski

@Vidda @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. – Declan

Your unit test implies that correct insertion point for e.g 4 is at -5 with arr = [1, 2, 2, 2, 5, 9, 11, (...)] Using Abs(index) will insert 4 between 5 and 9, which is wrong. How do you suggest using the insert point correctly? – Humanist

@Humanist To get the insertion point from the result, you should invert the return value: i = -i -1, or as others pointed out, i = ~i. I checked your example, and I see correct result: const el = 4; const input = [1, 2, 2, 2, 5, 9, 11]; i = binarySearch(input, el, (i, j) => {return i - j}); if (i < 0) {i = ~i}; out = [...input.slice(0, i), el, ...input.slice(i)]. The result: [1, 2, 2, 2, 4, 5, 9, 11] – Amine

Answer 3

Binary Search (ES6)

---

These functions return the element's position (index) within a sorted array if it was found or -1 if it wasn't.

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

const arr = [0,1,2,3,4,6,100,10000];

console.log(binarySearch(arr, 100)); // 6

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

const arr = [0,1,2,3,4,6,100,10000];

console.log(binarySearch(arr, 1000)); // -1

Harping

Answer 4

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.

Ahner

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. :-) – Barty

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. – Barty

@Barty 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 – Ahner

@Barty 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 ;) – Ahner

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. – Barty

@Barty 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 ;) – Ahner

What's the advantage of lo + ((hi - lo) >> 1 vs (hi + lo) >> 1? – Sweatbox

@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 ai.googleblog.com/2006/06/… – Ahner

@Ahner 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 – Sweatbox

@Sweatbox 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«. – Ahner

@Ahner 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. – Sclater

@Sclater 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. – Ahner

@Ahner 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.) – Sclater

@Sclater 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 ;-) – Ahner

Answer 5

𝗬𝗼𝘂 𝘄𝗮𝗻𝘁 𝘀𝗽𝗲𝗲𝗱? 𝗥𝗲𝗮𝗱 𝘁𝗵𝗶𝘀.

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://mcmap.net/q/94397/-binary-search-in-javascript
    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://mcmap.net/q/94397/-binary-search-in-javascript
    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://mcmap.net/q/94397/-binary-search-in-javascript
    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://mcmap.net/q/94397/-binary-search-in-javascript
      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://mcmap.net/q/94397/-binary-search-in-javascript
    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.

Lignite

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. ;) – Ahner

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… – Ahner

@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. – Lignite

@Ahner 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. – Lignite

…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. – Ahner

@Ahner Very good point. I cannot find any flaw in your logic. I wish I could loosen myself up about performance like you do. (+1) – Lignite

@Ahner To amend my plagiarism of your solution, I have revisited, revisited, and redone my entire answer. – Lignite

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). – Marchellemarcher

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 => 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...) – Marchellemarcher

Answer 6

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

Exodontics

Answer 7

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

Polyzoan

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. – Wretch

Answer 8

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)

Interfertile

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? – Measly

@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"! – Interfertile

Answer 9

Posting the answer if in case someone wants

1. Recursive and non-recursive way
2. 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));

Tadd

Answer 10

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

};

Tributary

Answer 11

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

Coracoid

Answer 12

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

Suppose

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 – Adar

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. – Suppose

Answer 13

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

Barrault

It would be good to simplify the code so that beginners can understand. – Kikelia

I wanted to give a version that builds on ES6 features. What don't you understand about it? – Barrault

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. – Lignite

Answer 14

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

Tripp

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. :) – Diapositive

Answer 15

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

Laura

Answer 16

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

Tarsia

Answer 17

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

Ruvalcaba

Answer 18

Instead of binary search you may simply consider a linear search with findIndex (or findLastIndex or find or findLast). Likely slower for large array, but less coding...

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

i = a.findIndex(x => x >= 4)

console.log(`a[${i}] = ${a[i]}`)

Of course the array must be sorted.

Septuagenarian

Answer 19

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

Underage

Recursive function calling = slow code; all day every day (pretty much no exceptions). – Lignite

@JackGiffin: Not to mention splice (explained here why it’s bad). Still upvoted for simplicity and didactic quality. – Sidsida

@Sidsida 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. – Lignite

@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”-tier. – Sidsida

Answer 20

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

Matriarchy

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. – Augury

Why are you returning the value that matches the target? That makes the whole search redundant! You should return the index. – Fontanel

Answer 21

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

Pylos

Why are you returning the value that matches the target? That makes the whole search redundant! You should return the index. – Fontanel

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. – Pylos

Answer 22

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

Yenyenisei

That slice may be elegant, but it is pretty unnecessary, and thus not very performant under these circumstances. – Lignite

Answer 23

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

Alrich

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 – Lignite

Answer 24

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

Disenchant

Answer 25

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

Decapod

Answer 26

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

Unused

Answer 27

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

Noxious

Answer 28

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/

Pileum

Answer 29

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.

Shepperd

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? – Preen

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. – Shepperd

So you're saying it may well change, thus link is better solution, as reader will see the most up to date version? – Preen

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. – Shepperd