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

Question

[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));

Comments

[WbICHA]

Так пройдитесь по шагам по своему алгоритму. Лучше дебаггером. Ошибка прямо на глазах.

[Олег]

Уточните ваш вопрос, Чего вы хотите добиться этим алгоритмом?

[aleks_web_dev]

Бинарный поиск но чет не работает
Она находит числа только до 5 потом ошибка

Answer 1

[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 элемет вы уже рассмотрели и он точно не нужен).

Comments

[aleks_web_dev]

Спасибо я как раз уже начал понимать что за херня получилась
Спасибо