@aleks_web_dev

Алгоритм работает не правильно?

находит числа до 5 поле сыпит ошибками о бесконечном цикле

function bin(arr, val) {
  let mid = Math.floor(arr.length / 2)

  while (mid >= 0 && mid <= arr.length) {

    if (arr[mid] === val) {
      return arr[mid]
    }

    if (arr[mid] > val) {
      mid = Math.floor(mid / 2)
    } 
    
    if (arr[mid] < val) {
      mid = Math.floor((arr.length - mid) / 2)
    }

  }
}


  console.log(bin([1, 2, 3, 4, 5, 6, 7, 8, 9,], 7));
  • Вопрос задан
  • 93 просмотра
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, гуглер, экс-олимпиадник.
Бинпоиск поддерживает текущий отрезок, в котором возможно есть искомый элемент. Смотрит на середину и отбрасывает одну из половин отрезка.

Вы же как-то пытаетесь реализовать это только лишь с переменной mid. Если надо идти влево, то вы делите mid пополам, как будто бы текущий отрезок от начала массива (Но это не всегда так: после первого же шага вправо начало массива будет уже выкинуто из расмотрения), Потом, при переходе вправо, у вас какой-то бред написан.
Math.floor((arr.length - mid) / 2) - это что вообще должно делать? Если mid=9, length = 10, вы вообще уйдете в начало массива, хотя должны идти вправо. Если вы хотели взять середину между mid и length, то там должен стоять "+" внутри.

Но так все-равно не получится сделать. Заведите 2 переменные l и r, как во всех реализациях бинпоиска, считайте mid как середину отрезка, и при выбрасывании одной из половин просто переписывайте l или r на mid+1 или mid-1 (потому что сам mid элемет вы уже рассмотрели и он точно не нужен).
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

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

Войти через центр авторизации
Похожие вопросы
от 75 000 до 180 000 ₽
Artezio Нижний Новгород
от 130 000 до 180 000 ₽
Artezio Москва
от 160 000 до 220 000 ₽
08 мар. 2021, в 10:02
75000 руб./за проект
08 мар. 2021, в 10:00
700 руб./за проект
08 мар. 2021, в 08:37
3000 руб./за проект