Неочевидная штука: Москва не резиновая Вместимость переменных конечна. Это значит, что (в нынешней данности - когда в одном байте, обычно, 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);
}
Как-то так :))))