Двоичный поиск или как найти то, чего нет. Скучнопост.
Неочевидная штука: Москва не резиновая Вместимость переменных конечна. Это значит, что (в нынешней данности - когда в одном байте, обычно, 8 бит) - в этот самый байт (BYTE) "влезет" 256 значений (при счёте с нуля это число [0,255]), в слово (WORD) влезет 65536 значений, в двойное слово (DWORD) 4294967296 и в счетверённое "слово" (на дворе "прогресс", 64 бита есть 64 бита) - дохуя, но не более 18446744073709551616 значений.
А ещё это значит, что разного рода числовые идентификаторы (от номера по-порядку, до Боец00000000000000000001 - Боец18446744073709551616) - конечны. И если в этом списке кого-то выпилили, образуется "дырка", которую можно и нужно использовать повторно.
Если числа невелики - поиск "в лоб" оправдан.
А если нет?
И тут можно вспомнить любимые игрища древних в децимацию дихотомию, которая нынче называется умным термином "двоичный поиск".
Как ищут известное? Сначала берём отсортированный список значений, затем - берут середину. Нашли? Да, победа, нашли. Нет? А искомое больше? Допустим, что да - берём правую часть от половины, ищем точно также там (повторяем). Нет? Не беда, берём левую (аналогично). И так - до победы до момента нахождения. Настолько просто, что нынче это стандартный алгоритм (тыкабельно) во всех уважающих себя библиотеках, прилагающихся к языкам программирования.
Но вот закавыка. А как быстро найти то, чего нет - отсутствующий элемент (ну, уж всяко быстрее, чем "в лоб", прямым перебором)?
И тут вот такой вот велосипед (если порвёт строки, я неуиноватый, филиал хабра здесь никто не обещал, формата для исходного кода не предусмотрено):
//Поиск пропуска в нумерации в последовательном списке с выработкой нового номера
//TList *ls - Сортированный список номеров int (правильно, а не лексикографически, т.е. 1,2,3...10,11)
//delta - первый минимальный номер, например 1 или 100001
int SearchGapId(TList *ls, const int delta)
{
int L = 0; //лево
int R = ls->Count - 1; //право
int M, MVal; //индекс середины и номер значения из середины
if(ls->Count == 0) //случай раз, список пуст - идём в конец, там получим номер
goto mRet;
if( (int(ls->Items[R]) - delta ) == R) //случай два, в списке нет "дырок" - идём в конец, там получим номер
{
L = R + 1;
goto mRet;
}
//список не пуст, "дырки" есть, ищем
//или "двоичный поиск дырки" - "найти то, чего нет"
while (L <= R) //крутимся в цикле, пока "слева" не переехало "справа"
{
M = (L + R)/2; //берём середину, можно было быстрее, но так нагляднее
MVal = int(ls->Items[M]) - delta; //берём значение, лежащее в списке под этим индексом
if (MVal > M) //магия :))))
R = M - 1;
else
L = M + 1;
}
mRet:
return (L + delta);
}
Как-то так :))))
Новые комментарии
BuhBuhov
14 часов назад
При чем тут я? Есть правила сайта, они и запрещают показывать без соответствующего тега.
konst
17 часов назад
Вот тебе и раз! И это говорит человек, который даже женскую грудь запрещает нейронкам показывать!
BuhBuhov
1 день назад
Целовались-то взасос. Вот если бы не обнимались, а потрахались, было бы интересно. ИИ-шница беспонтовая....
BuhBuhov
12 дней назад
Да какое может быть здоровье после десяти дней в больнице? Не разваливаюсь и ладно. 
На больничном вот сижу. Дрыхну по 10-12 часов. Очухиваюсь потихоньку.
BuhBuhov
14 дней назад
А можно мне той же дури, что курил автор?
Да, есть такое вино «Изабелла». Крайне дешёвое и исключительно вредное.
«Изабелла» это сорт винограда, а не вина. А вино полученное из этого сорта вполне может называться и по другому. Потому, как сорта винограда принято смешивать.
Впрочем, вино «Изабелла» весьма мною уважаемо и почему вдруг оно стало исключительно вредным — мне не понятно. Не более вредное чем любое другое вино. Зато с моей точки зрения, это одно из самых вкусных вин.
Admin
18 дней назад
видо добавить — просто ссылку скопируй и все, утебя там лишний символ был в начале, поэтому не получилось
konst
20 дней назад
Вот десятка лучших (только счас специально посмотрел), у всех намного дольше 7 секунд — №
Пилот
Очки
Сек
Дата
1
OborotovKonstantin s
397
39.71
2026-09-19 21:26:14
2
JasonWoorhies
380
38.03
2026-10-07 11:04:52
3
OborotovKonstantin s
378
37.86
2026-09-19 11:02:30
4
OborotovKonstantin s
360
36.03
2026-09-26 19:18:02
5
JasonWoorhies
348
34.82
2026-10-07 10:57:28
6
ОborotovКonstantin
345
34.52
2026-09-17 19:13:06
7
JasonWoorhies
307
30.77
2026-10-07 10:55:19
8
OborotovKonstantin Redmi14C
279
27.93
2026-09-13 16:58:49
9
OborotovKonstantin s
276
27.63
2026-09-19 15:10:18
10
Diman
240
24.02
2026-09-19 17:01:55
BuhBuhov
20 дней назад
Умер дед сегодня в реанимации....
Не успели, надо было раньше его туда.
А че почалось то? если надо для коду — мы добавим жеж:
Естественно, надо!!
А можно помедленнее и с картинками, пожалуйста?
Ну давай «на пальцах». Главное условие — список сортирован по возрастанию значений, т.е. 1,2,3....10,11… 100,101,… и т.п.
(допустим, что счёт с единицы)
Выдаём номер:
1. Список пуст. Выдаём минимальный номер. Возвращаем 0+1
2. Список не пуст. Последний элемент списка равен его «идеальному» порядковому номеру (т.е., грубо говоря, элемент с номером 100 содержит значение 100)? Нет. Значит дырок нет. возвращаем 100+1
3. Дырки есть, начинаем поиск. Лезем в середину. Элемент списка с номером 50 содержит 50? Да, дырка левее, нет, правее, повторяем, взяв нужную половину… В итоге мы найдём отсутствующий номер.
Хоть код и дан на c++ 98, но он вполне понятно читается, если читать :)
Блин, с «нет» и «да» заигрался. Перечитал — спохватился.
Было:
По смыслу понятно, но...
Читать так:
Разница колоссальна, от таких легкомысленных опечаток — не всегда просто ржач, иногда и на голову может упасть, извиняюсь за невнимательность, постараюсь расти над собой :)
А можно для самых маленьких вариант?
Вот есть у тебя список, содержащий номера 1,2,3,4,5
И вдруг №4 потребовалось удалить
Удалил… Образовался промежуток-«дырка», в списке остались такие номера 1,2,3,5
Причём «схлопнуть» эту дырку (особенно, когда список достаточно большой и следом за удалённым элементом ещё много других) — колоссальный труд, все «живые» элементы, которые остались в списке — уже пронумерованы, их нужно перенумеровывать, а это время и накладные расходы.
А теперь в этот список понадобилось новый элемент добавить.
И стало 1,2,3,5,6...
И если так делать слишком часто — никакой номерной ёмкости не хватит, да и всяческие ведомости странно выглядят, типа 1й, 3030й и Итого :)
Хорошо. Решил ты это дело как-то упорядочить. Хотя бы, чтобы если появится кто-то новенький — не назначать ему порядковый номер +1 от максимального, а запихнуть его в свободную «дырку».
Достичь этого просто. Нужно найти пустое место (и, если у нас всё по порядку, ближайшее к началу) и присвоить новенькому номер, как-то связанный с этим пустым местом.
Существует три основных способа:
1. Прямой перебор «в лоб». Берём каждую запись списка, узнаём номер который в ней содержится и, если следующая запись отличается от предыдущей больше, чем на единицу, то новенькому присваивается номер из предыдущей+1. Но это долго.
2. Вести ещё один список. При удалении любого элемента основного списка — в этот второй список записывать освободившийся номер. Но это не всегда нужные расходы
3. Двоичный поиск свободного промежутка. Т.к. мы каждый раз будем делить отрезок пополам — это будет достаточно быстро (лучше чем в 1, но хуже, чем в 2 случаях) и не требует места под хранение второго списка (лучше чем в 2 и также, как и в 1 случаях). Получается золотая середина.
Реализуем двоичный поиск.
Сначала нужно понять, как связаны индекс элемента (порядковый номер элемента в списке) и номер элемента (значение, номер, внутренний номер или идентификатор — ниже буду именовать как-то так).
Поскольку в сях (C, C++) нумерацию ведут с нуля, то пять элементов списка имеют индексы 0,1,2,3,4
Легко видеть, что между номерами и индексами есть прямая взаимосвязь.
0 = 1-1
1 = 2-1
2 = 3-1
3 = 4-1
4 = 5-1
Иначе говоря Индекс = Номер — Дельта
В данном случае, Дельта = 1
Также, у нас ситуация — мы удалили №4 (индекс 3), после чего список
Элемент 0 содержит №1
Элемент 1 содержит №2
Элемент 2 содержит №3
Элемент 3 содержит №5
И нам нужно выдать новый номер.
Как работает двоичный поиск дырки/промежутка.
Стоит понять заранее, нужно ли ли искать «дырку», когда нам понадобилось выдать новый номер?
Делаем две простых проверки:
1) Список совсем пуст. Тогда просто вернём дельту=1
2) Индекс последнего элемента списка совпадает с его номером (когда список был полон, то 4 = 5-1). Это значит, что можно сразу вернуть следующий номер, т.е. (4+1)+1
Не повезло, ищем.
Возьмём весь текущий отрезок значений L = 0 (индекс самого левого элемента списка), R = 3 (индекс самого последнего)
Повторяем блок действий:
Проверим, а действительно ли текущий левый индекс L не превышает текущий правый индекс R? 0<=3
Если нет — заканчиваем повторять.
Если да, работаем:
Возьмём середину на этом текущем отрезке отрезке M = (0+3)/2 = 1 (индекс элемента посредине)
/*единица, т.к. у нас целочисленное деление, тут даже округления нет, т.е. берётся целая часть*/
Возьмём значение, хранящееся в элементе с этим индексом MVal = Элемент[M] = Элемент[1] = 2
И приведём значение MVal в соответствие с индексом, чтобы можно было что-то с чем-то сравнить:
MVal = MVal — Дельта = 2 — 1 = 1
Получившееся MVal БОЛЬШЕ индекса M? (1>1? Нет)
Если да, это значит, что искомый промежуток-дырка находится в левой половине отрезка LR, Тогда выкидываем правую половину и сужаем наш отрезок справа, R = M — 1
Если нет, значит то, что мы ищем — находится в правой половине отрезка LR. Выкидываем левую половину и сужаем наш отрезок слева, L = M + 1
Повтор блока действий (L=2, 2<=3).
Возьмём середину на этом текущем отрезке отрезке M = (2+3)/2 = 2 (индекс элемента посредине)
Возьмём значение, хранящееся в элементе с этим индексом MVal = Элемент[M] = Элемент[2] = 3
И приведём значение MVal в соответствие с индексом, чтобы можно было что-то с чем-то сравнить:
MVal = MVal — Дельта = 3 — 1 = 2
Получившееся MVal БОЛЬШЕ индекса M? (2>2? нет)
Если да, это значит, что искомый промежуток-дырка находится в левой половине отрезка LR, Тогда выкидываем правую половину и сужаем наш отрезок справа, R = M — 1
Если нет, значит то, что мы ищем — находится в правой половине отрезка LR. Выкидываем левую половину и сужаем наш отрезок слева, L = M + 1
Повтор блока действий (L=3, 3<=3).
M = 3
MVal = 5
MVal-1 = 4
Получившееся MVal БОЛЬШЕ индекса M? (4>3? Да)
Если да, это значит, что искомый промежуток-дырка находится в левой половине отрезка LR, Тогда выкидываем правую половину и сужаем наш отрезок справа, R = M — 1
Если нет, значит то, что мы ищем — находится в правой половине отрезка LR. Выкидываем левую половину и сужаем наш отрезок слева, L = M + 1
Прекращение повтора блока действий (L=3, R=2, 3<=2? Нет)
Возвращаем L+Delta (3+1=4)
Примечание, на маленьких списках, скорее всего лучше будет перебор «в лоб».
Примечание2, пример специально так подобран, чтобы поиск работал подольше.
Большое вам спасибо за ваш полуночный немалый труд! Только сейчас допёр. А что затратнее внедрения подобного механизма или увеличение числа (в разумных пределах)?
Всё зависит от необходимости. Уже DWORD — переполнить «простым смертным» очень сложно. В принципе, задача повторного использования идентификаторов — штука специфическая. Ну так, если прикинуть, — на ум сходу приходят айпишники (особенно IPV4) и телефонные номера, где величины переменных увеличить сложновато :)
Иначе говоря, под каждую задачу — свой инструмент. Иногда решение «в лоб» — самое оправданное, а иногда может аукнуться спустя много лет, что приводит к написанию костылей. Короче, лучше пользоваться принципами разумной необходимости и не усложнять то, что усложнения не требует. Начинять задачу многоэтажными конструкциями «чтобы было» или «потому что могу» — уж точно не стоит :)