Skip to content
Advertisement

Improve speed of my binary search algorithm

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

Advertisement

Answer

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; }
User contributions licensed under: CC BY-SA
1 People found this is helpful
Advertisement