Я прочитал это: https://www.topcoder.com/community/competitive-programming/tutorials/binary-search. Я не могу понять некоторые части ==>
What we can call the main theorem states that binary search can be used if and only if for all x in S, p(x) implies p(y) for all y > x. This property is what we use when we discard the second half of the search space. It is equivalent to saying that ¬p(x) implies ¬p(y) for all y < x (the symbol ¬ denotes the logical not operator), which is what we use when we discard the first half of the search space.
Но я думаю, что это условие не выполняется, когда мы хотим найти элемент (только проверка на равенство) в массиве, и это условие выполняется только тогда, когда мы пытаемся найти неравенство, например, когда мы ищем элемент больше или равен к нашему целевому значению.
Пример: мы находим 5 в этом массиве.
indexes=0 1 2 3 4 5 6 7 8 1 3 4 4 5 6 7 8 9
мы определяем p(x)=>
if (a[x]==5) return true else return false
первый шаг => средний индекс = 8+1/2 = 9/2 = 4 ==> a[4]=5 и p (x) верно для этого, и из основной теории результат таков, что p(x+1) ........ p(n) верно, но это не так.
Так в чем проблема?
«Теорема» утверждает, что вы не можете использовать бинарный поиск с этим предикатом в этом массиве.
@molbdniloЯ не могу понять, пожалуйста, объясните подробнее.
@AiraBanazadeh В теореме утверждается, что требование к массиву и предикату для бинарного поиска возможно. (Неофициально здесь не говорится «если вы выполняете поиск, массив имеет это свойство», а говорится «если массив имеет это свойство, вы можете выполнить поиск».) Ваш массив и предикат не удовлетворяют этим требованиям (p(5)
верно, но p(6)
ложно), поэтому вы не можете использовать их для бинарного поиска.
Мы МОЖЕМ использовать эту теорему при поиске точного значения, потому что мы
используйте его только тогда, когда отбрасывание одна половина. Если мы ищем, скажем, 5,
и мы находим, скажем, 6 в середине, мы можем отбросить верхнюю половину,
потому что теперь мы знаем (благодаря теореме), что всех предметов там > 5
Также обратите внимание, что если у нас есть отсортированная последовательность и мы хотим найти любой элемент
который удовлетворяет неравенству, достаточно взглянуть на конечные элементы.
Но я думаю, что мы можем использовать бинарный поиск и в других ситуациях. Например, мы можем использовать его, когда мы хотим получить первый элемент в нашем отсортированном массиве, который больше или равен точному значению. ( >= свойство)
@AiraBanazadeh Двоичный поиск найдет элемент один с требуемым свойством, если таковой существует, не обязательно первым. Например, поиск >= 1
в {1,2,3,4,5}
найдет 3
.
Ну, они сказали
which is what we use when we discard the first half of the search space.
, а вы сказалиthis condition does not hold when we want to find an element
. Это как ходить по кругу. ? В бинарном поиске есть еще 2 условия, о них надо говорить.