Основная теория дискретного бинарного поиска

Я прочитал это: 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) верно, но это не так.

Так в чем проблема?

Ну, они сказали 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 условия, о них надо говорить.

Rahul 22.05.2019 13:30

«Теорема» утверждает, что вы не можете использовать бинарный поиск с этим предикатом в этом массиве.

molbdnilo 22.05.2019 13:38

@molbdniloЯ не могу понять, пожалуйста, объясните подробнее.

Aira Banazadeh 22.05.2019 13:42

@AiraBanazadeh В теореме утверждается, что требование к массиву и предикату для бинарного поиска возможно. (Неофициально здесь не говорится «если вы выполняете поиск, массив имеет это свойство», а говорится «если массив имеет это свойство, вы можете выполнить поиск».) Ваш массив и предикат не удовлетворяют этим требованиям (p(5) верно, но p(6) ложно), поэтому вы не можете использовать их для бинарного поиска.

molbdnilo 22.05.2019 13:53
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
2
4
173
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Мы МОЖЕМ использовать эту теорему при поиске точного значения, потому что мы
используйте его только тогда, когда отбрасывание одна половина. Если мы ищем, скажем, 5,
и мы находим, скажем, 6 в середине, мы можем отбросить верхнюю половину,
потому что теперь мы знаем (благодаря теореме), что всех предметов там > 5

Также обратите внимание, что если у нас есть отсортированная последовательность и мы хотим найти любой элемент
который удовлетворяет неравенству, достаточно взглянуть на конечные элементы.

Но я думаю, что мы можем использовать бинарный поиск и в других ситуациях. Например, мы можем использовать его, когда мы хотим получить первый элемент в нашем отсортированном массиве, который больше или равен точному значению. ( >= свойство)

Aira Banazadeh 22.05.2019 16:31

@AiraBanazadeh Двоичный поиск найдет элемент один с требуемым свойством, если таковой существует, не обязательно первым. Например, поиск >= 1 в {1,2,3,4,5} найдет 3.

molbdnilo 23.05.2019 07:18

Другие вопросы по теме