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

Question

[dmitry-toster]

Нужно посчитать сколько будет сделано шагов, чтобы исключить половину чисел у определенного числа
Напр., у числа 100 это 7 шагов

у 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)
По логике надо возвращать ф-ю которая поделит число напополам и вернет шаги, вроде все логично, но почему-то у меня слегка зудит от этой строчки

Answer 1

[Karpion]

Бинарный поиск также называет "писк делением пополам". Попробуем пойти с конца.

1. На последнем этапе мы имеем массив из двух элементов, после деления которого получаем решение - найденный нужный элемент или же понимание того, что нужного элемента в массиве нет.
   
2. На предпоследнем этапе мы имеем массив из четырёх элементов, который поделим и получим массив из двух элементов. Или м.б. массив из трёх элементов - тогда этот шаг м.б. предпоследним или последним.
   
3. И так на каждом шаге размер массива удваивается.
   

Т.о., за k шагов мы можем разделить массив, имеющий 2^**k элементов. Тогда k=log₂(n), т.е. речь идёт о логарифме_по_основанию_два.
Если же n не является степенью двойки - то k=roundup(log₂(n)), т.е. мы округляем дробное число до целого вверх. log₂(100)=6.644, с округлением вверх получаем семь.

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

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

Comments

[dmitry-toster]

Благодарю за потраченное время на объяснение. Кнута явно не осилю, может когда-нибудь в будущем, но точно не сегодня. Знакомство с алгоритмами начал с книги "Грокаем алгоритмы", не классика, но по отзывам весьма хороша

[Karpion]

Кнута не надо осиливать целиком. Его надо прочитать, вникая в понятное и пропуская непонятное.

Очень хороша книга - Никлаус Вирт, "Алгоритмы и структуры данных".

И очень советую найти человека для живого общения, чтобы задавать ему вопросы.

Answer 2

[Александр Маджугин]

М... так это же просто логарифм по основанию 2, округленный в большую сторону. Зачем вообще какие-то программы писать?

Comments

[dmitry-toster]

логарифм по основанию 2

буквы знакомые, слова ни разу (

Зачем вообще какие-то программы писать?

начал читать книжку по алгоритмам

[Александр Маджугин]

dmitry-toster, прям так и загугли что это.
Вычислить в твоем случае надо как-то так: Math.ceil(Math.log2(100))

[Karpion]

dmitry-toster, Если Вы не понимаете выражение "логарифм по основанию два", то Вам очень трудно будет стать хорошим программистом...

Для Вашего примера - Вы получили число 7.
2^**6=64
2^**7=128 (два в степени семь = 2*2*2*2*2*2*2 = 128)
128 как раз первое число в ряжу степеней двойки, которое больше, чем сто.
Так понятно?

[dmitry-toster]

Александр Маджугин, загуглил. статья из разряда "ничего не понял, но очень интересно". с моим неокрепшим нематематическим умом за один вечер явно не осилю, но знать как оно называется уже достижение.

[dmitry-toster]

Karpion, понятно, спасибо. Только в момент задания вопроса было не понятно как вычислить это кол-во двоек. Для этого и писал свою функцию, даже не подозревая о существовании готовых формул (от того, что не знал как это даже прогуглить). Можете ваше объяснение опубликовать ответом- отмечу решением
UPD:

Если Вы не понимаете выражение "логарифм по основанию два", то Вам очень трудно будет стать хорошим программистом...

Будете смеяться - только на 4 год в этой профессии я понял, что мне не хватает подобных фундаментальных знаний, посему и начал изучать алгоритмы и паттерны. Но судя по тому, что я понял ваше объяснение, надеюсь не все еще потеряно...

[Александр Маджугин]

dmitry-toster, к 8 году поймешь что их не только не хватает, они еще и нахрен не нужны.

[dmitry-toster]

Александр Маджугин,

[Александр Маджугин]

dmitry-toster, в прикладной разработке знание алгоритмов нужно очень редко, и то чаще всего только для того, чтобы понять как обойти какое-нибудь узкое место.
Даже понимание сложности алгоритмов, достаточно иметь интуитивное. Не надо знать что О(n^3) это то же самое что O(n^2). Достаточно понимать что O(n) это сильно лучше чем O(n^k).

[dmitry-toster]

Александр Маджугин, почему же тогда все так топят за эти алгоритмы, что без их знаний не стать хорошим программистом и тд? Я их начал изучать, чтобы они научили меня думать, что в будущем поспособствует написанию менее костыльного кода, разве не это их побочный эффект от обучения?

[Александр Маджугин]

dmitry-toster, я вам напомню, что изучая эти самые алгоритмы, вы только что написали велосипед на костылях для Math.ceil(Math.log2(n)) на 15 строк кода.

Знание алгоритмов не спасет от костылей, поскольку костыли возникают не из-за их незнания, а от нехватки опыта или времени.

Безусловно знать базовые алгоритмы и иметь представление об их сложности полезно. Но как я уже сказал выше - вряд ли они вам понадобятся на практике. Особенно в начале пути.

[dmitry-toster]

Александр Маджугин, чем тогда отличается программист, который решает задачу за час от программиста, который решает эту же задачу за сутки? Только наличием опыта? И знание алгоритмов закрывать таски быстрее первому никак не помогает?

[Александр Маджугин]

На мой взгляд именно "закрывать быстрее" не помогает.
Иногда помогает в принципе закрывать.

Представьте вы грузчик. Полезно иметь грузчику права на электрокар? Полезно, без сомнения.
Помогают ли они быстрее разгрузить машину? Ну если использование электрокара целесообразно и он вообще есть на том предприятии где работает этот грузчик - то да.
Во всех остальных случаях коих 90% вряд ли.
И если вы желая устроится грузчиком пойдете получать права на электрокар вместо физподготовки, то насколько рационален будет такой шаг?

Answer 3

[hzzzzl]

а зачем байндить, там же никак не используется this и прочее вот это вот всё,
return counter(stepNumber) так же вернет 7 для 100

а вообще countSteps = n => Math.ceil(Math.log2(n)) (но это неточно, я уже не особо в ладах с математикой)

Comments

[dmitry-toster]

да, ведь и вправду...
return counter(stepNumber)
и
countSteps(100)
вместо

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

что-то я понамутил с этими замыканиями... стыдобища. спасибо!

[hzzzzl]

dmitry-toster я бы как-то так написал тогда

function count(n) {
  if (n <= 0) return 0

  let curr = 0
  let steps = 0

  while(curr < n) {
    steps++
    curr = 2 ** steps   // = Math.pow(2, steps)
  }

  return steps
}

[dmitry-toster]

hzzzzl, тоже интересное решение, благодарю

[Александр Маджугин]

но это неточно, я уже не особо в ладах с математикой

Это точно.