@dmitry-toster

Бинарный поиск — как определить кол-во шагов?

Нужно посчитать сколько будет сделано шагов, чтобы исключить половину чисел у определенного числа
Напр., у числа 100 это 7 шагов
5f46b2959a506719076082.jpeg
у 240 000 - 18
и тд...
Я написал функцию и она вроде как работает:
const countSteps = n => {
    let steps = 0
    let stepNumber = n

    const counter = halfNumber => {
        if (Math.round(stepNumber) > 1) {
            steps++
            stepNumber = stepNumber / 2

            counter(stepNumber)
        }

        return steps
    }

    return counter.bind(null, stepNumber)
}

const steps100 = countSteps(100)
steps100() // 7

Есть какие-то замечания как ее можно улучшить? Например, это:
return counter.bind(null, stepNumber)
По логике надо возвращать ф-ю которая поделит число напополам и вернет шаги, вроде все логично, но почему-то у меня слегка зудит от этой строчки
  • Вопрос задан
  • 116 просмотров
Решения вопроса 3
М... так это же просто логарифм по основанию 2, округленный в большую сторону. Зачем вообще какие-то программы писать?
Ответ написан
hzzzzl
@hzzzzl
а зачем байндить, там же никак не используется this и прочее вот это вот всё,
return counter(stepNumber) так же вернет 7 для 100

а вообще countSteps = n => Math.ceil(Math.log2(n)) (но это неточно, я уже не особо в ладах с математикой)
Ответ написан
@Karpion
Бинарный поиск также называет "писк делением пополам". Попробуем пойти с конца.
  1. На последнем этапе мы имеем массив из двух элементов, после деления которого получаем решение - найденный нужный элемент или же понимание того, что нужного элемента в массиве нет.
  2. На предпоследнем этапе мы имеем массив из четырёх элементов, который поделим и получим массив из двух элементов. Или м.б. массив из трёх элементов - тогда этот шаг м.б. предпоследним или последним.
  3. И так на каждом шаге размер массива удваивается.
Т.о., за k шагов мы можем разделить массив, имеющий 2**k элементов. Тогда k=log2(n), т.е. речь идёт о логарифме_по_основанию_два.
Если же n не является степенью двойки - то k=roundup(log2(n)), т.е. мы округляем дробное число до целого вверх. log2(100)=6.644, с округлением вверх получаем семь.

Что такое "логарифм" - программист должен знать. Без этого хороший код писать не получится - будет тупо непонятно описание алгоритмов.

Очень советую почитать книги классиков: Кнут, Вирт и прочие. Там не про современные системы программирования, а именно про алгоритмы - не зависящие ни от архитектуры компьютера, ни от языка программирования. Старые книги хороши тем, что прошли проверку временем. Хотя, конечно, там могут отсутствовать некоторые знания, полученные недавно. Зато там нет (или очень мало) откровенного фуфла, которого много в современных книжках.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

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

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