Вот есть у тебя список, содержащий номера 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, пример специально так подобран, чтобы поиск работал подольше.