Улучшить скорость моего алгоритма бинарного поиска - PullRequest
Новая
       12

Улучшить скорость моего алгоритма бинарного поиска

0 голосов
/ 03 марта 2020

Я написал бинарный алгоритм поиска в 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;
}

Я хотел спросить, могу ли я улучшить этот алгоритм для более быстрого поиска или если здесь допущена какая-то ошибка?

РЕДАКТИРОВАТЬ:

спасибо, ребята, за вашу помощь, теперь это решение должно работать правильно: 

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

Ответы [ 2 ]

0 голосов
/ 03 марта 2020

Вы принимаете значения в качестве индексов. Если вы принимаете больше значений, чем индексы, вы видите, что ваши коды не работают.

Вместо этого вы можете взять индекс middle для left или right, если не найден. 

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; }
0 голосов
/ 03 марта 2020

Облегчите 

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