Закрученная история о двоичном поиске

1656585623 zakruchennaya istoriya o dvoichnom poiske

автор Девья Годайал

1*DClFFS2kX-MPvGuHYvOyTw
Источник: https://www.pinterest.com/pin/261912534550561245/?lp=true

Прекрасно. Именно так я чувствую себя сейчас. Пишу свою первую солотехническую статью.

Должен сказать, что мне есть чем поделиться с вами, ребята, и еще многому поучиться. Так что без лишних промедлений давайте приступим к этому. И так, держись крепко — потому что в сказке есть поворот. ?

Все мы слышали о классической проблеме «2 яйца и 100 историй». У меня для вас есть нечто подобное.

У вас есть 100-этажное здание с правилом:

People with pets can only occupy top floors

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

Строительство в отпуске. На каждом этаже возле лифта есть табличка, указывающая, можно на этаже с домашними животными или нет. Но вам лень останавливаться на каждом этаже, чтобы проверить табличку с домашними животными, поскольку лифт очень медленный.

Что ты делаешь?

1*mVvYhywAIoa11tCRfsHPQA
Две возможные вывески. #GoRed – это то, за что болеет ваш друг.

Подъемник на каждом этаже останавливается, а затем снова запускается. Да, как это плохо. Но между этажами навигация достаточно плавная. Вы должны сделать это быстро.

Как ты к этому относишься?

Итеративный подход

Одним из наивных подходов к этому было бы начинать с самого низа здания (первого этажа) и продолжать останавливать лифт на каждом отдельном этаже, чтобы проверить висящий на этаже знак. Вы останавливаетесь, когда найдете знак «Разрешает с животными».

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

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

Худший случай Сценарий состоит в том, что вы достигнете 100-го этажа, останавливаясь на каждом этаже на пути вверх, только чтобы узнать, что во всем здании нет табличек с домашними животными. Ваш друг может купить любую квартиру от 1 до 100, но кого это волнует, вам понадобилось почти два часа, чтобы это узнать. ? ?.

Алгоритмически, если учесть массив из 100 логических значений, индекс массива представляет этажи здания, а 0 обозначает этаж, где не разрешены домашние животные, а 1 представляет этаж, на котором разрешено размещение домашних животных. Согласно правилу здания, массив выглядел бы

000... 1111...

то есть все нули, за которыми следуют все 1, поскольку только верхние этажи могут быть теми, где разрешено размещение домашних животных.

Учитывая этот массив, нам нужно найти первый индекс, где есть a 1 . Алгоритм линейного поиска для этой проблемы будет таким же простым, как итерация по массиву и поиск 1 и возвращаемся, когда найдем.

Как и ожидалось, сложность этого алгоритма будет O(n) где n=100 для нашего конкретного примера здания. Вам нужно придумать что-нибудь быстрее, чем это. Останавливаться на каждом этаже невозможно, поскольку в худшем случае вам понадобится много времени, чтобы охватить все здание.

Бинарный поисковый подход

Предположим, вы начали с первого этажа и добрались до 50 этажа без остановок. На 50-м этаже вы остановились, вышли из лифта и проверили, есть ли знак. На табличке написано “No Pets”. Это означало бы, что до 50-го этажа, безусловно, нет домашних животных.

Теперь зная, что вы уменьшаете свое поисковое пространство до второй половины, а это 51–100 этажи. Это значит, что за одну остановку вы смогли охватить половину строения, точно зная, что в первой половине нет домашних животных. Это удивительно!

Двигаясь дальше, вы снова делите ваш набор оставшихся этажей пополам, поднимаетесь на лифте и следуете на 75 этаж. И вы видите а “Pets” там вывеска. Это означает, что поверхность, где она начала появляться, должна быть между 50-75. Вы можете продолжать придерживаться аналогичного подхода, разделяя остальные этажи пополам и проверяя, пока не найдете первый этаж с помощью “Pets” вывеска.

Понимаете, каждый раз, когда вы принимаете решение, вы делите свое поисковое пространство на две половины и продолжаете использовать одну половину пространства поиска. Таким образом, мы сужаем наш поиск. Поскольку мы всегда делим пространство поиска пополам и выбираем одно над другим, поэтому этот тип стратегии поиска называется Binary Стратегия поиска.

Разве это не резвее?

Давайте разберемся в алгоритме этого.

1*5xqxb4gs88vQGaK8CCp47w
Алгоритм двоичного поиска

Если бы вы внимательно следили за этим и имели понимание алгоритма, вы поняли бы жесткое и быстрое условие для работы алгоритма двоичного поиска. Условие состоит в том, что массив нужно предварительно отсортировать. В нашем примере этажи здания были отсортированы от 1 до 100 и мы могли легко разделить пространство поиска на два.

Давайте посмотрим на пример отсортированного массива и попытаемся найти в нем элемент.

1*sCdkKU8RqA6_R3uiy4nL2w

В вышеприведенном примере элементом для поиска является 8. Данный массив является отсортированным массивом в порядке возрастания. Как только мы найдем средний элемент (равный 5), мы видим, что элемент, который нужно искать, больше текущего элемента индекса. Поскольку массив отсортирован в порядке возрастания, 8 будет лежать справа от массива и никогда не может быть слева.

Поэтому мы игнорируем элементы слева от 5 и продолжаем наш поиск с другими элементами, наконец находя 8.

1*S2lDovD5HeUsdSHm3NM4Sw

С другой стороны, что делать, если массив не отсортирован? Несмотря на то, что мы знаем, что текущий элемент равен 5 и мы знаем, что нам нужно искать 8, мы не уверены, в каком направлении следует двигаться. Если мы в конечном счете подумаем, что массив отсортирован, применим двоичный поиск и перейдем к нужной части, мы никогда не найдем 8.

Таким образом, двоичный поиск по существу хочет, чтобы ваш массив был отсортирован.

Это был стандартный алгоритм двоичного поиска, который мы только что рассмотрели. Но, как следует из названия статьи, в сказке есть поворот!

Я упорный конкурентоспособный программист, и у CodeChef May Long Challenge был интересный вариант алгоритма бинарного поиска.

В сущности, Шеф написал классический двоичный поиск, предполагая, что входной массив будет отсортирован. Все остальные дети в классе скопировали с него код, поскольку Шеф – лучший программист в классе. Его предположение могло стоить всему классу оценок присвоения, поскольку входной массив не был отсортирован заранее.

Единственное, что может сделать шеф-повар, это предварительно обработать массив, сменяя местами некоторые пары чисел здесь и там, чтобы процедура двоичного поиска все еще возвращала правильный индекс.

1*MOupjMd8PLQIkCoXHPIkHw

Примечание: В идеале вышеприведенный препроцессор должен возвращать измененный массив, чтобы двоичный поиск работал правильно. Однако, как задается в формулировке проблемы, мы просто пытаемся определить количество свопов, необходимых для корректной работы двоичного поиска в несортированном массиве с учетом входных данных. Алгоритм также возвращает –1, если такая модификация невозможна для данного массива и элемента.

Идея здесь очень проста.

Нам нужно понять два основных шага. Я называю их TI-ME шаги. Возможно, это поможет вам вспомнить, что мы делаем здесь.

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

б. Мпростоя ЕКрик: если вы посмотрите четко в двоичном поиске, это средний элемент текущего пространства поиска, который управляет следующим шагом. Если этот средний элемент ведет нас в неправильном направлении, нужно заменить соответствующим элементом.

1*xgnYQLeH-9l2MVU_OqTNLQ
Мы ищем 8 в приведенном выше несортированном массиве. В вышеприведенных примерах мы уже видели, что обычный двоичный поиск не удастся для несортированного массива.
1*sJNU_8PdNlbIuy7RStVHdA
Средние элементы дают направление бинарному поиску. Средний элемент 5 требует двоичного поиска, чтобы идти вправо. Такого пути мы никогда не найдем 8. If we swap 5 with an element greater than 8 we would force the search to go to left.

Итак, вся идея состоит в том, что мы поменяем местами все неправильно размещенные средние элементы.

Алгоритм двоичного поиска (значение среднего элемента по отношению к элементу, который нужно искать, то есть X) может привести нас к левой половине массива или правой половине. Итак, есть две возможности для неправильно размещенного среднего элемента:

  1. Элемент, который нужно искать, находился справа от среднего элемента, но с тех пор Element[Mid] > Element[Target Index], двоичный поиск должен игнорировать правую половину и двигаться к левой половине. ИЛИ
  2. Элемент, который нужно искать, находился слева от среднего элемента, но с тех пор Element[Mid] < Element[Target Index], двоичный поиск должен игнорировать левую половину и двигаться к правой половине.

Следовательно, если средний элемент неправильно расположен так, что число X требовалась на своем месте, где X < Element[Target Index], тогда мы поддерживаем счетчик для этого и вызываем it count_low_neeдед.

Аналогично, если средний элемент неправильно расположен так, что число X требовалась на своем месте, где X > Element[Target Index], тогда мы поддерживаем счетчик для этого и вызываем it count_high_neeдед.

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

Давайте сначала рассмотрим псевдокод этого алгоритма, а затем рассмотрим пример.

function can_preprocess(arr, X){     low = 0     high= 0
while X is not found {          mid = (low + high) / 2          if arr[mid] == X {             break                     }
correctly_placed_low = 0          correctly_placed_high = 0          count_low_needed = 0          count_high_needed = 0
if `mid` suggests we should go right for X {               if X is actually on the right {                   correctly_placed_low ++               }               else {                   count_low_needed ++               }          } else {               if X is actually on the left {                  correctly_placed_high ++               }                else {                  count_high_needed ++               }          }
modify low and high according to           where `X` actually is with respect to `mid`
}
// Total smaller numbers available for swapping     TSM = sorted_index[X] - correctly_placed_low
// Total Larger numbers available for swapping     TLM = (N - sorted_index[X]) - correctly_placed_high
if count_low_needed > TSM or count_high_needed > TLM {          return -1     }
return max(count_low_needed, count_high_needed)

ПРИМЕЧАНИЕ: Постановка проблемы исправляет входящий массив для нас и многократно передает значение для поиска во входящем массиве. Итак, мы можем один раз пройтись по исходному массиву, чтобы узнать фактическое расположение элемента, который нужно искать (по сути, создать словарь).

Также нам нужно sorted_index[X] чтобы сказать нам, сколько значений меньше или больше элемента X в нашем массиве. Мы можем отсортировать массив и создать другой словарь, в котором хранится каждый элемент в отсортированном массиве.

Давайте пройдемся по шагам предложенного метода во время сухого выполнения примера.

  1. Учитывая несортированный массив, нужно искать X = 4 .
    Поэтому наш целевой индекс равняется 7.
1*3vnVPsJgCPjLLmWENiB8rQ

2. Средний индекс элемента ut Element[Mid] > Element[Target указатель], hence count_low_needed = 1

1*goOz9sCtElJn8_GVf86n-Q

3. Средний индекс элемента n, Element[Mid] > Element[Target указатель], hence count_low_needed = 2

1*RuHR_k66dh-G0KzI-6DRuQ

4. Общее количество свопов, необходимых для двоичного поиска, чтобы вернуть правильный индекс здесь, будет двумя заменами с элементами менее 4. У нас есть меньшие числа 1, 3 or 2 доступная замена, поэтому мы можем успешно произвести замену для этого массива, чтобы двоичный поиск правильно нашел 4 .

Ниже приведен код Python для данной проблемы. Каждый шаг разъясняется в комментариях.

Временная сложность этого алгоритма Twisted Binary Search все еще остается O(nlogn) .

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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *