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

Я прочитал это: 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
3 метода стилизации элементов HTML
3 метода стилизации элементов HTML
Когда дело доходит до применения какого-либо стиля к нашему HTML, существует три подхода: встроенный, внутренний и внешний. Предпочтительным обычно...
Формы c голосовым вводом в React с помощью Speechly
Формы c голосовым вводом в React с помощью Speechly
Пытались ли вы когда-нибудь заполнить веб-форму в области электронной коммерции, которая требует много кликов и выбора? Вас попросят заполнить дату,...
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Будучи разработчиком веб-приложений, легко впасть в заблуждение, считая, что приложение без JavaScript не имеет права на жизнь. Нам становится удобно...
Flatpickr: простой модуль календаря для вашего приложения на React
Flatpickr: простой модуль календаря для вашего приложения на React
Если вы ищете пакет для быстрой интеграции календаря с выбором даты в ваше приложения, то библиотека Flatpickr отлично справится с этой задачей....
В чем разница между Promise и Observable?
В чем разница между Promise и Observable?
Разберитесь в этом вопросе, и вы значительно повысите уровень своей компетенции.
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Клиент для URL-адресов, cURL, позволяет взаимодействовать с множеством различных серверов по множеству различных протоколов с синтаксисом URL.
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

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