LINUX.ORG.RU

Двоичный поиск, математика

 


0

1

Добрый день!

Я новичок, поэтому вопросы у меня соответствующие.

Я услышала на одной из онлайн лекций, что согласно алгоритму двоичного поиска (binary search) если, например, есть 4 милларда данных в телефонной книге, то найти нужного человека по имени (например, Kim Smith) можно за 32 шага. Если удвоить количество данных до 8 млрд, то потребуется 33 шага.

Я понимаю алгоритм (делим попалам, затем еще попалам нужные половины пока не надем), но я плохо владею математикой и не понимаю как получаются 32 и 33 шага, и тем более log(n). Пожалуйста, подскажите где можно про это прочитать и изучить (не в Википедии)?

Спасибо!


Я понимаю алгоритм (делим попалам, затем еще попалам нужные половины пока не надем), но я плохо владею математикой и не понимаю как получаются 32 и 33 шага, и тем более log(n).

Тут всё просто. log(n) по основанию 2 — это то, в какую степень нужно возвести 2 для того, чтобы получить n. То есть,

log(n) = 32
отсюда n = 2^32
И 32 шага получаются потому, что делишь ты постоянно на 2. А 2^32 = 4294967296, то есть, около 4 миллиардов

Deleted ()
Ответ на: комментарий от hope13

нет ) возможность мозга - для меня там очень сложно написано. Спасибо за ссылки.

Ducol ()

Алгоритм интересный, но с точки зрения применимости крайне ненужный, так как упорядоченные данные редко имеем.

unt1tled ★★★★ ()
Ответ на: комментарий от unt1tled

ну, сначала отсортировать за nlog(n), а потом уже искать :-)

gnunixon ★★★ ()
Ответ на: комментарий от unt1tled

крайне ненужный

так как упорядоченные данные редко имеем

Лол.

intelfx ★★★★★ ()
Последнее исправление: intelfx (всего исправлений: 1)

Это легко можно понять, взяв карандаш и бумажку, и начав симуляцию алгоритма с поиска одного из двух вариантов.

thesis ★★★★★ ()
Ответ на: комментарий от unt1tled

но с точки зрения применимости крайне ненужный

Я постоянно пользую питонячий bisect даже в говновебе.

A1 ()
Ответ на: комментарий от unt1tled

так как упорядоченные данные редко имеем.

intelfx хоть и школие, но это действительно лол. Как по твоему работают B-tree индексы?

A1 ()
Ответ на: комментарий от unt1tled

Алгоритм интересный, но с точки зрения применимости крайне ненужный, так как упорядоченные данные редко имеем.

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

m0rph ★★★★★ ()
Ответ на: комментарий от m0rph

мне даже интересно стало, сколько людей используют в работе алгоритмы поиска по сортированным данным, вместо встроенных contains() или get()

unt1tled ★★★★ ()
Последнее исправление: unt1tled (всего исправлений: 1)
Ответ на: комментарий от unt1tled

вместо встроенных contains() или get()

Встроенных куда? Это важный вопрос в свете того, что структура данных может быть таблица, дерево, список, хэш-таблица. Этим ты хотел сказать, что тебе все равно, что за структура данных используется?

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

Сложность O(n) тебя не смущает? Окай.

iVS ★★★★★ ()
Ответ на: комментарий от unt1tled

но с точки зрения применимости крайне ненужный, так как упорядоченные данные редко имеем

который так же внезапно каждый день пишет половина лора?

Одно дело нужность алгоритма, и совсем другое - нужность велосипедостроения. А так можно сказать, что вообще программирование ненужное занятие, т.к. «всё уже украдено до нас».

no-such-file ★★★★★ ()
Ответ на: комментарий от no-such-file

Ладно, поставим вопрос подругому: сколько лоровцев имеют честь постоянно искать что-то в b-tree? Можно даже опрос запилить.

unt1tled ★★★★ ()
Последнее исправление: unt1tled (всего исправлений: 1)
Ответ на: комментарий от unt1tled

Однако часто встречаются данные, которые редко меняются, зато по ним нужно часто искать. В таком случае выгодно их отсортировать один раз и запомнить (а при добавлении новых элементов вставлять их на такие позиции, чтобы сортировка не портилась), а потом искать двоичным поиском.

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

KivApple ★★★★★ ()
Последнее исправление: KivApple (всего исправлений: 2)
Ответ на: комментарий от unt1tled

Ладно, поставим вопрос подругому: сколько лоровцев имеют честь постоянно искать что-то в b-tree?

Понимаешь, что сейчас ты показал уровень редчайшей безграмотности в структурах данных. Сортировка и поиск — это binary-search tree (BST). B-tree — из другой области. Естественно, что лоровцы ничего не ищут в B-tree, но могут искать в BST. B-tree — оптимизированная версия деревьев под размер кэша, ты ею пользуешься практически постоянно, обращаясь к оперативке или диску.

iVS ★★★★★ ()
Последнее исправление: iVS (всего исправлений: 1)
Ответ на: комментарий от unt1tled

Если ты работаешь с hashmap, map, set и другими подобными типами в твоём любимом недоязычке, у меня для тебя плохие новости.

hateyoufeel ★★★★★ ()
Ответ на: комментарий от unt1tled

я использую.

было это лет 5 назад.

срочно вызывают на обьект, а там вся сеть упала изза arp-шторма. откуда идет шторм не понятно. сеть простая, компов 30, коммутатор простой на 48 портов.

что делать? как быстро найти виновника?

все порты на коммутаторы поделили на левые и правые.

отключили левую половину сети, оставили только правую, проблема пропала.

выключили левую часть.

правую часть снова поделили на левую и правую.

провели несколько итерации и в итоге нашли нерабочий компьютер.

после этого случая на этом обьекте я стал звездой.

вот польза от двоичного поиска.

Nurmukh ★★★ ()
Ответ на: комментарий от anto215

Причем тут динамический вариант дерева? Как будто бы на статическом поиск не делается?

iVS ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.