Есть две причины для бинарного поиска с одним сравнением на итерацию.
менее важным является производительность. Раннее определение точного соответствия с использованием двух
Сравнение на одну итерацию сохраняет в среднем одну итерацию цикла, тогда как
(при условии, что сравнение требует значительных усилий) бинарный поиск с одним
сравнение за итерацию почти вдвое сокращает объем работы, выполненной за итерацию.
Бинарный поиск в массиве целых чисел, это, вероятно, не имеет большого значения
в любом случае. Даже при довольно дорогом сравнении асимптотически
производительность такая же, и скорее половина-чем-минус один, вероятно, не стоит
преследуя в большинстве случаев. Кроме того, дорогостоящие сравнения часто кодируются как функции, которые возвращают отрицательное, нулевое или положительное значение для <, == или >, поэтому в любом случае вы можете получить оба сравнения почти по цене одного.
Важной причиной выполнения двоичного поиска с одним сравнением на итерацию является
потому что вы можете получить более полезные результаты, чем просто какое-то совпадение. Главный
поиск, который вы можете сделать, это ...
- Первый ключ> цель
- Первый ключ> = цель
- Первый ключ == цель
- Последний ключ <цель </li>
- Последний ключ <= цель </li>
- Последний ключ == цель
Все они сводятся к одному базовому алгоритму. Понимание этого достаточно хорошо
что вы можете легко кодировать все варианты не так уж сложно, но я не
действительно видел хорошее объяснение - только псевдокод и математические доказательства. это
моя попытка объяснения.
Есть игры, в которых идея состоит в том, чтобы максимально приблизиться к цели
без перерегулирования. Измените это на «undershooting», и вот что «Найти»
Первый> "делает. Рассмотрим диапазоны на некотором этапе во время поиска ...
| lower bound | goal | upper bound
+-----------------+-------------------------+--------------
| Illegal | better worse |
+-----------------+-------------------------+--------------
Необходимо найти диапазон между текущей верхней и нижней границей.
Наша цель (обычно) где-то там, но мы еще не знаем, где.
Интересным моментом в отношении предметов выше верхней границы является то, что они являются законными в
ощущение, что они больше цели. Можно сказать, что элемент просто
выше текущей верхней границы - наше лучшее на сегодняшний день решение. Мы можем даже сказать это
в самом начале, хотя, вероятно, в этой позиции нет ни одного предмета - в
смысл, если нет действительного решения в диапазоне, лучшее решение, которое не имеет
было опровергнуто только за верхней границей.
На каждой итерации мы выбираем элемент для сравнения верхней и нижней границ.
Для бинарного поиска это округленный промежуточный элемент. Для поиска двоичного дерева это
продиктовано структурой дерева. Принцип одинаков в любом случае.
Поскольку мы ищем элемент, превосходящий нашу цель, мы сравниваем тестовый элемент
используя Item [testpos] > goal. Если результат ложный, у нас есть промах (или
недооценка) наша цель, поэтому мы сохраняем наше лучшее на данный момент решение и корректируем
наша нижняя граница вверх. Если результат верен, мы нашли новый лучший пока что
решение, поэтому мы корректируем верхнюю границу вниз, чтобы отразить это.
В любом случае, мы никогда не хотим снова сравнивать этот тестовый элемент, поэтому мы корректируем
обязано исключить (только просто) тестовый элемент из диапазона для поиска. бытие
небрежное отношение к этому обычно приводит к бесконечным циклам.
Обычно используются полуоткрытые диапазоны - включающая нижняя граница и исключительная
верхняя граница. Используя эту систему, элемент в верхнем граничном индексе не находится в
диапазон поиска (по крайней мере, не сейчас), но - лучшее решение на данный момент. Когда ты
переместите нижнюю границу вверх, переместите ее на testpos+1 (чтобы исключить элемент, который вы только что
проверено из ассортимента). Когда вы перемещаете верхнюю границу вниз, вы перемещаете ее в
testpos (верхняя граница в любом случае исключительна).
if (item[testpos] > goal)
{
// new best-so-far
upperbound = testpos;
}
else
{
lowerbound = testpos + 1;
}
Когда диапазон между нижней и верхней границами пуст (используя полуоткрытый
когда оба имеют одинаковый индекс), ваш результат - ваш самый последний лучший
решение, чуть выше верхней границы (т. е. на верхний предел индекса для
полуоткрытый).
Таким образом, полный алгоритм ...
while (upperbound > lowerbound)
{
testpos = lowerbound + ((upperbound-lowerbound) / 2);
if (item[testpos] > goal)
{
// new best-so-far
upperbound = testpos;
}
else
{
lowerbound = testpos + 1;
}
}
Чтобы перейти с first key > goal на first key >= goal, вы буквально переключаетесь
оператор сравнения в строке if. Относительный оператор и цель могут быть заменены одним параметром - функцией предиката, которая возвращает true, если (и только если) ее параметр находится на стороне, превышающей цель.
Это дает вам "first>" и "first> =". Чтобы получить «first ==», используйте «first> =» и
добавить проверку на равенство после выхода из цикла.
Для "последнего <" и т. Д. Принцип такой же, как и выше, но диапазон
отражение. Это просто означает, что вы меняете границы настроек (но не
комментарий) а также смена оператора. Но прежде чем сделать это, рассмотрим следующее ... </p>
a > b == !(a <= b)
a >= b == !(a < b)
Кроме того ...
- позиция (последний ключ <цель) = позиция (первый ключ> = цель) - 1
- позиция (последний ключ <= цель) = позиция (первый ключ> цель) - 1
Когда мы перемещаем наши границы во время поиска, обе стороны движутся к цели, пока не встретятся у цели. И прямо под нижней границей есть специальный предмет, точно так же, как над верхней границей ...
while (upperbound > lowerbound)
{
testpos = lowerbound + ((upperbound-lowerbound) / 2);
if (item[testpos] > goal)
{
// new best-so-far for first key > goal at [upperbound]
upperbound = testpos;
}
else
{
// new best-so-far for last key <= goal at [lowerbound - 1]
lowerbound = testpos + 1;
}
}
Таким образом, у нас есть два дополнительных поиска, выполняющихся одновременно. Когда встречаются верхняя и нижняя границы, у нас есть полезные результаты поиска на каждой стороне этой единственной границы.
Для всех случаев есть вероятность, что этот оригинальный "мнимый" за пределами
лучшая на данный момент позиция была вашим конечным результатом (в
диапазон поиска). Это необходимо проверить перед выполнением окончательной проверки ==
первый == и последний == случаи. Это также может быть полезным поведением - например, если
Вы ищете позицию для вставки цели, добавляя ее после
конец ваших существующих предметов - это то, что нужно делать, если все существующие предметы
меньше вашей цели.
Пара замечаний по выбору тестовых заданий ...
testpos = lowerbound + ((upperbound-lowerbound) / 2);
Во-первых, это никогда не будет переполнено, в отличие от более очевидного ((lowerbound +
upperbound)/2). Он также работает с указателями и целыми числами
индексы.
Во-вторых, предполагается, что деление округляется вниз. Округление вниз для неотрицательных
все в порядке (все, что вы можете быть уверены в C), так как разница всегда неотрицательна
в любом случае.
Это один аспект, который может потребоваться, если вы используете не-полуоткрытый
диапазоны - убедитесь, что тестовая позиция находится внутри диапазона поиска, а не только снаружи (на одной из уже найденных наилучших на данный момент позиций).
Наконец, при поиске в двоичном дереве неявное перемещение границ и
выбор testpos встроен в структуру дерева (которое может быть
несбалансированный), но те же принципы применяются для того, что делает поиск. В этом
В этом случае мы выбираем наш дочерний узел, чтобы уменьшить неявные диапазоны. Для первого матча
В случаях, когда мы нашли новое меньшее совпадение (перейдите к младшему ребенку в надежде найти еще меньший и лучший вариант) или мы промахнулись (перейдем к старшему ребенку в надежде на выздоровление). Опять же, четыре основных случая могут быть обработаны путем переключения оператора сравнения.
Кстати - есть больше возможных операторов для использования с этим параметром шаблона. Рассмотрим массив, отсортированный по году, а затем по месяцу. Может быть, вы хотите найти первый предмет для определенного года. Для этого напишите функцию сравнения, которая сравнивает год и игнорирует месяц - цель сравнивается как равная, если год равен, но значение цели может отличаться от ключа, который даже не имеет значения месяца, чтобы сравнить. Я считаю это «частичным сравнением ключей» и включаю его в шаблон двоичного поиска, и вы получаете то, что я считаю «частичным поиском ключей».
РЕДАКТИРОВАТЬ В нижеследующем абзаце говорилось "31 декабря 1999 года будет равно 1 февраля 2000 года". Это не сработает, если весь диапазон между ними также не будет считаться равным. Дело в том, что все три части дат начала и конца диапазона отличаются, поэтому вы не имеете дело с «частичным» ключом, но ключи, считающиеся эквивалентными для поиска, должны образовывать непрерывный блок в контейнере, что обычно подразумевает непрерывный блок в упорядоченном наборе возможных ключей.
Это не просто "частичные" ключи. Ваше пользовательское сравнение может считать 31 декабря 1999 года равным 1 января 2000 года, но все остальные даты отличаются. Дело в том, что пользовательское сравнение должно согласовываться с исходным ключом в отношении упорядочения, но оно может быть не столь разборчивым при рассмотрении всех различных значений по-разному - оно может рассматривать диапазон ключей как «класс эквивалентности».
Дополнительное примечание о границах, которые я действительно должен был включить раньше, но я, возможно, не думал об этом в то время.
Один из способов оценки границ состоит в том, что они вообще не являются индексами item . Граница - это граничная линия между двумя элементами, поэтому вы можете нумеровать граничные линии так же легко, как нумеровать элементы ...
| | | | | | | | |
| +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ |
| |0| | |1| | |2| | |3| | |4| | |5| | |6| | |7| |
| +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ |
| | | | | | | | |
0 1 2 3 4 5 6 7 8
Очевидно, что нумерация границ связана с нумерацией предметов. До тех пор, пока вы нумеруете свои границы слева направо и точно так же, как вы нумеруете свои элементы (в данном случае, начиная с нуля), результат будет фактически таким же, как и общее полуоткрытое соглашение.
Можно было бы выбрать среднюю границу, чтобы разделить диапазон точно на две части, но это не то, что делает бинарный поиск. Для бинарного поиска вы выбираете элемент для тестирования, а не границы. Этот элемент будет проверен в этой итерации и никогда не должен проверяться снова, поэтому он исключен из обоих поддиапазонов.
| | | | | | | | |
| +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ |
| |0| | |1| | |2| | |3| | |4| | |5| | |6| | |7| |
| +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ |
| | | | | | | | |
0 1 2 3 4 5 6 7 8
^
|<-------------------|------------->|
|
|<--------------->| | |<--------->|
low range i hi range
Таким образом, testpos и testpos+1 в алгоритме - это два случая перевода индекса элемента в связанный индекс. Конечно, если две границы равны, в этом диапазоне нет элементов для выбора, поэтому цикл не может продолжаться, и единственный возможный результат - это одно связанное значение.
Показанные выше диапазоны - это всего лишь диапазоны, которые еще предстоит найти - разрыв, который мы намереваемся сократить между диапазонами доказанного ниже и доказанного выше.
В этой модели бинарный поиск ищет границу между двумя упорядоченными типами значений - теми, которые классифицируются как «более низкие», и теми, которые классифицируются как «более высокие». Тест предикатов классифицирует один элемент. Не существует «равного» класса - равные ключу значения являются частью более высокого класса (для x[i] >= key) или более низкого класса (для x[i] > key).