@justifycontent

Верно ли написал бинарный поиск?

const binarySearch = (list, n) => {
    let start = 0,
        end = list.length - 1,
        mid;
    
    while(start <= end) {
      mid = Math.floor((start + end) / 2);
      if (n < list[mid]) {
        end = mid - 1;
      } else if (n > list[mid]) {
        start = mid + 1;
      } else {
        return `Искомое ${n} найдено на ${mid} индексе(${list[mid]})`;
      }
    }

    return `Искомое ${n} не найдено!`;
  }
  • Вопрос задан
  • 193 просмотра
Решения вопроса 1
user_of_toster
@user_of_toster
mid = Math.floor((start + end) / 2);
Можно не расчитывать заранее и писать только внутри цикла while

n !== list[mid]
Если нужное значение посередине, то ваш бинарный поиск сломается. Это условие нужно удалить, т.к есть
else {
        return `Искомое ${n} найдено на ${mid} индексе(${list[mid]})`;
      }


mid !== start && mid !== end
Здесь из-за floor могут возникнуть баги, и поиск может закончиться раньше. Лучше заменить на start <= end
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
jcmvbkbc
@jcmvbkbc
http://dilbert.com/strip/1998-08-24
Верно ли написал бинарный поиск?

Не, неверно. Попробуй им найти 1 в массиве {0, 1}.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы