Программирование Жемчуг: Столбец 9.3 Бинарный поиск - диапазон инициализации

Question

В разделе 9.3 Job Bentley представляет модифицированный бинарный поиск.

краткое описание типичной реализации и лучшего подхода, показанного в 9.3

if (arr[mid] < key) low = mid+1
else if (arr[mid] > key) high = mid-1
else return mid;

модифицированное / эффективное сравнение с другим инвариантом.

if (arr[mid] < key) low = m;
else high = m;

И вне цикла есть проверка, если ключ в индексе "высокий". В модифицированном бинарном поиске левый индекс "низкий" начинается с -1 (вместо 0), а "высокий" индекс начинается с n (вместо n-1).. и цикл выполняется

while (low + 1 != high)

Этот модифицированный поиск, кажется, работает, даже если я установил низкий = 0 и высокий = n-1.

Но я бы предпочел не догадываться, Джоб Бентли в своем коде Так почему же он установил низкое значение -1 и высокое значение n? Есть ли случай, когда только это будет работать?

Answer 1

Если у вас есть массив, который пуст (n == 0), затем проверка while(low + 1 != high) будет корректно завершаться только в том случае, если low начинается в -1 а также high в 0,

while((-1 + 1) != 0) //true

Если low началось в 0 вместо или high началось в -1 (или оба), тогда цикл четко выполнит хотя бы одну проверку:

• while((0 + 1) != 0) // false
• while((-1 + 1) != -1) // false
• while((0 + 1) != -1) // false

Эта одна проверка пустого массива, скорее всего, получит доступ к индексу вне границ, который вызывает неопределенное поведение.