Javascript - Binary Search Hangs Every Time

I have a 2D array, something like the following: [1.11, 23] [2.22, 52] [3.33, 61] ... Where the array is ordered by the first value in each row. I am trying to find a value withi

Solution 1:

Your binary search seems to be a bit off: try this.

var arr = [[1,0],[3,0],[5,0]];

var lo = 0;
var hi = arr.length;

var x = 5;
var sensitivity = 0.1;

while (lo < hi) {
    var c = Math.floor((lo + hi) / 2);
    if (Math.abs(arr[c][0] - x) <= sensitivity) {
        hit = true;
        console.log("FOUND " + c);
        break;
    } elseif (x > arr[c][0]) {
        lo = c + 1;
    } else {
        hi = c;
    }
}

---

This is meant as a general reference to anyone implementing binary search.

Let:

• lo be the smallest index that may possibly contain your value,
• hi be one more than the largest index that may contain your value

If these conventions are followed, then binary search is simply:

while (lo < hi) {
    var mid = (lo + hi) / 2;

    if (query == ary[mid]) {
        // do stuffelseif (query < ary[mid]) {

        // query is smaller than mid// so query can be anywhere between lo and (mid - 1)// the upper bound should be adjusted

        hi = mid;
     else {

        // query can be anywhere between (mid + 1) and hi.// adjust the lower bound

        lo = mid + 1;
}

Solution 2:

I don't know your exact situation, but here's a way the code could crash:

1) Start with an array with two X values. This array will have a length of 2, so a = 0, b = 1, c = 0.

2) a < b, so the while loop executes.

3) c = floor((a + b) / 2) = floor(0.5) = 0.

4) Assume the mouse is not within sensitivity of the first X value, so the first if branch does not hit.

5) Assume our X values are to the right of our mouse, so the second if branch enters. This sets a = c, or 0, which it already is.

6) Thus, we get an endless loop.