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

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

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

log(n) = 32
отсюда n = 2^32

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

не в Википедии

религия не позволят?

http://neerc.ifmo.ru/wiki/index.php?title=Целочисленный_двоичный_поиск

http://cppstudio.com/post/2996/

Большое спасибо!

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

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

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

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

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

Лол.

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

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

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

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

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

причем тут B-tree?

причем тут B-tree?

Упорядоченные данные с логарифмическим поиском.

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

Упорядоченные данные с логарифмическим поиском.

что ты несешь?

Прими два курса Седжвика.

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

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

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

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

Которые внезапно используют двоичный поиск в упорядоченном дереве.

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

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

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

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

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

я вообще никогда не работаю с сортированными данными, а кому-то тут везде b-tree мерещатся

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

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

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

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

я ищу, правда не в b-tree, а в trie )

Ну вот и зачем ты пришел? Все, вопрос снят, я сливаюсь.

ну не знаю, поделиться радостью штоле

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

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

а потом искать двоичным поиском

Для равномерно распределенных данных есть и более быстрые алгоритмы.

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

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

https://en.wikipedia.org/wiki/Red-black_tree

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

я использую.

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

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

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

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

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

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

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

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

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

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

я всего лишь отвечал на это

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

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