Improve speed of my binary search algorithm

Question

I have written a binary search algorithm in JavaScript:

function binarysearch(number, array) {
  let left = 0;
  let right = array.length - 1;
  let middle;

  while (right != left) {

    middle = Math.floor(left + (right - left) / 2);
    if (array[middle] == number) {
      return middle;
    }
    if (array[middle] < number) {
      left = array[middle];
      if (array[middle + 1] == number) {
        return middle + 1;
      }
    }
    if (array[middle] > number) {
      right = array[middle];
      if (array[middle - 1] == number) {
        return middle - 1;
      }
    }
  }
  return -1;
}

I wanted to ask if I can improve this algorithm to search faster or if some mistake is made here?

EDIT:

thank you guys for your help, this solution should work correctly now:

function binarysearch(number, array) {
      let left = 0;
      let right = array.length - 1;
      let middle;
      while (left <= right) {
        middle = Math.floor(left + (right - left) / 2);
        if (array[middle] == number) {
          return middle;
        }
        if (array[middle] < number) {
          left = middle + 1;
        }
        if (array[middle] > number) {
          right = middle - 1;
        }
      }
      return -1;
    }

If the code is working as intended this would be better suited for [Code Review](https://codereview.stackexchange.com). — mkrieger1, Mar 03 '20 at 08:41
But does it work? `left` and `right` are indices into the array, but they are assigned array values. The bounds are inclusive, so it should probably be `left = middle + 1` and `right = middle - 1`. The additional checks at `middle ± 1` are not useful and look as if they are papering over the real problem. — M Oehm, Mar 03 '20 at 08:43
@MOehm it works, i tested it with a sorted array of 100 million numbers, and it gives me the correct index. if it doesnt find it gives me -1 back. i tested it vs an linear search with an `for` loop and it is much faster. i compared it with `performance.now()` the time is around `0.12` vs around `102` — , Mar 03 '20 at 08:48
I'm astonished to hear that it works. The code looks broken. I've just tried to find all numbers from 0 to 20 in the array `[3, 5, 7, 8, 9, 12, 14, 16]` and I get an infinite loop. What does your test look like? A million consecutive numbers, starting at 1? That _could_ work, given that you mix up array values and indices and would explain the spurious `+ 1` strewn about. — M Oehm, Mar 03 '20 at 08:51
i see got an infinity loop too. i just made an `for` loop, and for each loop iteration it pushes its iteration into the array `array.push(i)` up to 100 million , and then i search an number. — , Mar 03 '20 at 08:55
That's a very special case. You were only interested in making it big, but you need to test some edge cases, too: Search on an empty array (in which case your `right` is −1, ouch!), search for elements outside the range of the array, an array with gaps, an array with duplicated elements, ... Linear search is slow, but it's faster than an infinite loop. `:)` — M Oehm, Mar 03 '20 at 09:12
https://stackoverflow.com/questions/39416560/how-can-i-simplify-this-working-binary-search-code-in-c/39417165#39417165 — Matt Timmermans, Mar 03 '20 at 12:46

score 0 · Accepted Answer · answered Mar 03 '20 at 09:29

You are taking values as indices. If you take greater values than indices, you see your codes does not work.

Instead, you could take the index of middle for left or rightif not found.

function binarysearch(number, array) {
    let left = 0,
        right = array.length - 1,
        middle;

    while (left <= right) {
        middle = Math.floor((left + right) / 2);
        if (array[middle] === number) return middle;
        if (array[middle] > number) right = middle - 1;
        else left = middle + 1;
    }
    return -1;
}

console.log(binarysearch(0, [43, 44, 45, 46, 47, 48, 49, 50]));
console.log(binarysearch(43, [43, 44, 45, 46, 47, 48, 49, 50]));
console.log(binarysearch(44, [43, 44, 45, 46, 47, 48, 49, 50]));
console.log(binarysearch(45, [43, 44, 45, 46, 47, 48, 49, 50]));
console.log(binarysearch(46, [43, 44, 45, 46, 47, 48, 49, 50]));
console.log(binarysearch(47, [43, 44, 45, 46, 47, 48, 49, 50]));
console.log(binarysearch(48, [43, 44, 45, 46, 47, 48, 49, 50]));
console.log(binarysearch(49, [43, 44, 45, 46, 47, 48, 49, 50]));
console.log(binarysearch(50, [43, 44, 45, 46, 47, 48, 49, 50]));
console.log(binarysearch(100, [43, 44, 45, 46, 47, 48, 49, 50]));

.as-console-wrapper { max-height: 100% !important; top: 0; }

score -1 · Answer 2 · answered Mar 03 '20 at 08:59

-1

Make it easier

  let left = 0;
  let right = array.length - 1;
  let middle;

  while (right != left) {

    middle = Math.floor(left + (right - left) / 2);
    if (array[middle] == number) {
      return middle;
    }
    if (array[middle] < number) {
      left = array[middle] + 1;
    }
    if (array[middle] > number) {
      right = array[middle];
    }
  }
  return -1;
}

answered Mar 03 '20 at 08:59

Вадим Калищук

55
1
6

Yes, that's easier. Unfortunately, this function suffers from the same problems as OP's code: It mixes up array indices and values. It should be `left = middle + 1`, for example. You should also make up your mind whether you want to use inclusive upper bounds, in which case it's `right = middle - 1` or exclusive upper bounds, in which case it's just `right = array.length`. Given that Javascript uses exclusive upper bounds for arrays, I'd prefer the latter. – M Oehm Mar 03 '20 at 09:08

Improve speed of my binary search algorithm

2 Answers2