Разница между основным двоичным поиском верхней и нижней границ?
В статье http://community.topcoder.com/tc?module=Static&d1 = учебники&d2 = BinarySearch, Автор обсуждает бинарный поиск. Он проводит различие между поиском наименьшего значения, где что-то верно, и наивысшего значения, где что-то ложно.
Разыскиваемый массив выглядит примерно так:
ложно ложно ложно верно верно
Мне любопытно, почему эти два случая различны. Почему вы не можете просто найти самое низкое значение, которое является истинным, а затем вычесть одно, чтобы найти самое высокое значение, которое является ложным?
Edit2: хорошо, так что я понимаю нижнюю или верхнюю границу. Теперь я пытаюсь понять, при поиске наименьшего целого числа, большего или равного запросу, почему мы не можем просто изменить if(mid>query) в if(mid>=query) и сделать это сделать ниже, а не верхнюю границу.
Редактировать: вот что говорится в статье:
«Теперь мы наконец добрались до кода, который реализует бинарный поиск, как описано в этом и предыдущем разделе:
binary_search(lo, hi, p):
while lo < hi:
mid = lo + (hi-lo)/2
if p(mid) == true:
hi = mid
else:
lo = mid+1
if p(lo) == false:
complain // p(x) is false for all x in S!
return lo // lo is the least x for which p(x) is true
…
Если бы мы хотели найти последний x, для которого p (x) ложно, мы разработали (используя аналогичное объяснение, как указано выше) что-то вроде:
binary_search(lo, hi, p):
while lo < hi:
mid = lo + (hi-lo+1)/2 // note: division truncates
if p(mid) == true:
hi = mid-1
else:
lo = mid
if p(lo) == true:
complain // p(x) is true for all x in S!
return lo // lo is the greatest x for which p(x) is false
.»
Решение
Нижняя и верхняя граница бинарного поиска — это самая низкая и самая высокая позиции, в которые значение может быть вставлено без нарушения порядка. (В стандартной библиотеке C ++ эти границы будут представлены итераторами, ссылающимися на элемент, перед которым значение может быть вставлено, но концепция по существу не изменилась.)
Взять, к примеру, отсортированный диапазон
1 2 3 4 5 5 5 6 7 9
В двоичном поиске 3, Мы будем иметь
v-- lower bound
1 2 3 4 5 5 5 6 7 9
^-- upper bound
И в двоичном поиске 5:
v-- lower bound
1 2 3 4 5 5 5 6 7 9
^-- upper bound
Нижняя и верхняя границы совпадают, если элемент не существует в диапазоне. В двоичном поиске 8:
v-- lower bound
1 2 3 4 5 5 5 6 7 9
^-- upper bound
Автор статьи, на которую вы ссылаетесь, формулирует все это в эквивалентных терминах «меньше чем» и «больше чем», так что при поиске 5,
v-- lower bound
t t t t f f f f f f <-- smaller than?
1 2 3 4 5 5 5 6 7 9
f f f f f f f t t t <-- greater than?
^-- upper bound
Итераторы C ++ во всех этих случаях будут ссылаться на элемент непосредственно за границей. То есть:
- В поисках
3итератор возвращаетсяstd::lower_boundбудет относиться к3и один изstd::upper_boundбудет относиться к4 - В поисках
5итератор возвращаетсяstd::lower_boundбудет относиться к первому5и один изstd::upper_boundбудет относиться к6 - В поисках
8, оба будут относиться к9
Это связано с тем, что в стандартной библиотеке C ++ для вставок принято передавать итератор, ссылающийся на элемент, перед которым должен быть вставлен новый элемент. Например, после
std::vector<int> vec { 1, 3, 4, 5, 5, 5, 6, 7, 9 };
vec.insert(vec.begin() + 1, 2);
vec будет содержать 1, 2, 3, 4, 5, 5, 5, 6, 7, 9, std::lower_bound а также std::upper_bound следовать этой конвенции, чтобы
vec.insert(std::lower_bound(vec.begin(), vec.end(), 5), 5);
vec.insert(std::upper_bound(vec.begin(), vec.end(), 8), 8);
работай как хочешь и уходи vec отсортирован.
В более общем смысле это выражение способа определения диапазонов в стандартной библиотеке C ++. Начальный итератор диапазона ссылается на первый элемент диапазона (если есть), а конечный итератор ссылается на элемент (если есть) непосредственно за концом диапазона. Другой способ взглянуть на это состоит в том, что итераторы возвращаются std::lower_bound а также std::upper_bound охватывают диапазон элементов в искомом диапазоне, которые эквивалентны искомому элементу.
Этот диапазон пуст, если элемент не находится в диапазоне, так что lower_bound а также upper_bound вернуть тот же итератор, а в противном случае lower_bound возвращает итератор, ссылающийся на первый элемент в искомом диапазоне, который эквивалентен поисковому значению, в то время как upper_bound возвращает итератор, ссылающийся на элемент (если есть), который находится непосредственно за последним таким элементом.
Другие решения
Если массив всегда будет
false … true …
Тогда индекс перед найденным вами всегда будет ложным, если вы не найдете истину в index 0, Другой граничный случай, как упоминалось в моем комментарии выше, это если вы не найдете true, Тогда наибольшее ложное значение будет последней частью массива.
Эти два алгоритма, очевидно, различаются по условию того, что должно произойти, если нет true или нет false значение, как на самом деле вполне очевидно из фрагмента кода: если вы найдете самое низкое значение, где значение true и вычтите 1 из этой позиции, чтобы найти наибольшее значение, дающее false неверный результат получается, так как нет такого объекта. Поскольку алгоритмы просто нацелены на разные элементы, имеющие дело с непосредственным нахождением соответствующего элемента, а не с особым случаем, также избегают необходимости иметь дело с особым случаем, уменьшая объем кода. Поскольку код специального случая имеет тенденцию выполняться только один раз для каждого вызова алгоритма, он, вероятно, будет работать немного хуже, чем избегать специального случая. Это то, что может стоить измерения.
Обратите внимание, что пример кода не C ++, несмотря на вопрос, помеченный как C ++. В результате это не идиоматический C ++. Типичный подход в C ++ для реализации чего-то вроде lower_bound() или же upper_bound() это использовать соответствующие итераторы. Эти алгоритмы не будут «жаловаться», если нет подходящего элемента, так как они просто создадут итератор в соответствующей позиции, то есть итератор в начале для std::lower_bound() и последний итератор для std::upper_bound(),