Как же все-таки правильно написать двоичный поиск?

    В обсуждениях статьи Только 10% программистов способны написать двоичный поиск так никто и не написал, как же правильно подойти к решению этой задачи.
    Если мы не хотим использовать циклический метод «гадание, затем тестирование, затем исправление ошибок», то без инварианта цикла здесь не обойтись.
    Инвариант цикла – это соотношение, которое истинно перед циклом, истинно в процессе выполнения цикла и истинно при выходе из цикла. Все это описано у Дейкстры в книге «Дисциплина программирования», и детально разжевано у Гриса в книге «Наука программирования». Тем не менее, по моим наблюдениям, на практике этот метод практически НИКТО не использует, считая, что все это к реальности не имеет никакого отношения. Это большая ошибка.

    Сам Бентли c. 51 приводит такой инвариант: «если элемент T вообще есть в массиве X[1..N], то он должен быть в некоторой области, принадлежащей X». Первоначально эта область – весь массив.
    Формулировка эта — довольно невнятная. Думаю, причина этого в том, что у Бентли мало опыта – он, как и многие, использует всю это теорию только для обучения, а не для реальной жизни.
    Когда я читал книгу Бентли (давно) и дошел до слов «Чтобы вы поверили этому – отложите прямо сейчас эту книгу и попытайтесь написать программу сами» – я прикрыл книгу и довольно быстро нашел нормальную формулировку.
    Определим по краям массива область О так, чтобы она не содержала искомый элемент T. Это и будет инвариантом цикла: «в области О не содержится искомый элемент T».
    Первоначально эта область состоит из двух несмежных кусков нулевой длины (толщины, если угодно) в начале и в конце массива. Она не содержит искомый элемент, т. к. пуста и вообще ничего не содержит.
    Если в процессе работы эта область покроет весь массив, то искомого элемента в массиве нет.

    Формальная запись (буквы и размерность массива 1..N как у Бентли):
    Aj: 1 <=j < L или U < j <= N: X[j] != T
    Первоначально L=1, U=N, область пуста.
    Когда область покроет весь массив? Когда L > U, можно нарисовать и проверить по клеточкам. Это условие будет использовано для выхода из цикла.

    Теперь о содержимом цикла. Предположим, средний элемент (обозначим его индекс как M) массива X не равен искомому элементу T. Как мы можем изменить L и U так, чтобы инвариант остался истинным? В такой постановке задача оказывается настолько простой, что здесь негде ошибиться. Если T больше среднего элемента, то во всем куске от 1 до среднего элемента нет T. Аналогично, если T меньше среднего элемента, то во всем куске от среднего элемента до N нет T. Область расширяется, в первом случае L:=M+1, во втором U:=M-1.

    Обратите внимание, что все основные моменты алгоритма, а именно: условие «L>U» для выхода из цикла (отрицание «L<=U» — для продолжения), изменение границ области L:=M+1, U:=M-1 мы вывели не гаданием, а строгими, при этом очень простыми рассуждениями.

    Вот результирующий алгоритм на псевдокоде:

    L := 1; U := N; found := false; 
    while (L <= U) & not found do 
      M := середина отрезка L..U; 
      if a[M] = T then
        found := true;
      elseif a[M] < T then
        L := M+1;
      else
        U := M-1;
      end;
    end
    
    Поделиться публикацией
    Комментарии 23
      0
      Если внимательно читали статью, там ссылка на Википедию с корректной реализацией.
        +3
        По-моему тут в статье совсем о другом речь — а именно — не о конкретной реализации, а о том как же ее написать без использования тестирования.

        Очень интересно — за 20+ лет программинга — не встречался с «инвариантом цикла». И если это действительно поможет решить эту задачу без тестирования — это очень-очень интересно.

        Написано, конечно, сложно, перечитываю уже который раз, пытаюсь вникнуть.
          0
          «Aj: 1 <= j < L или U < j <= N: X[j] != T»

          А можно тут пояснения в текст добавить?
          Что такое «Aj»?
          Что такое «j»?
          Куда делать область «О»?

          И как-то надо тут расставить скобочки, а то не понятно:

          то ли «Aj = ( (1 <= j < L) или (U < j <= N)); X[j] != T;»
          то ли «Aj = ( ((1 <= j < L) или (U < j <= N)) И (X[j] != T))»
          то ли еще что-то…
          • НЛО прилетело и опубликовало эту надпись здесь
            • НЛО прилетело и опубликовало эту надпись здесь
              • НЛО прилетело и опубликовало эту надпись здесь
                  0
                  Пипец. Это же надо было автору так ужасно написать…
                    0
                    Здорово изобразили, спасибо.
                    Надо бы подправить статью, но можно ли сделать это задним числом? А то вдруг какой-нибудь дубль появится.
                    • НЛО прилетело и опубликовало эту надпись здесь
              0
              Да читал, конечно. Код приведен просто для полноты картины, иначе была бы какая-то незаконченность.
                0
                Спасибо за статью. Будет кармы достаточно — перенесите лучше в публичный, например в "Алгоритмы" — больше людей увидит.
              • НЛО прилетело и опубликовало эту надпись здесь
                +1
                Шикарно! 10 минут осмысления. 5 минут рисования на бумажке и задача становится тривиальной!
                  +1
                  Помимо сохранения инварианта важный элемент реализации — конечность времени работы. В вашем коде это гарантируется постоянным уменьшением интервала либо установкой флага found, но в самой статье об этом моменте практически ничего не сказано. А между тем на моей памяти большинство неправильных реализаций двоичного поиска именно зависали, а не выдавали неверный ответ.
                    –1
                    читал читал, но так и не вкурил, насколько это объяснение проще чем «охота на льва методом дихотомии»?

                    а вообще странно это. я по образованию не программист ни разу, про то что «двоичный поиск» это нечто фундаментальное не слышал ни разу, даже термин такой не знал до недавнего времени, но подобные задачи кажутся тривиальными. возможно это потому что когда нам читал курс «вычислительных методов… бла-бла… матеметике» мне попалась отличная книжка с кучей разобранных алгоритмов и реализацией на фортране…
                      +2
                      И при этом вы затратили в 2 раза больше сравнений. А все дело в том, что вы мыслите в человеческих терминах, а не в компьютерно-математических. Наилучший объект для разбиения на 2 части с точки зрения математики — полуоткрытый интервал. Алгоритм становится таким (для 0-based массивов):
                      // бинарный поиск, который ищет не только элемент, но и границу снизу.
                      L=0;R=N;
                      if (T<a[0]) //во многих случаях априори известно, что a[0]<=T и это можно опустить
                      {
                         lindex=-1;
                         found=false;
                         return;
                      }
                      // invariant: a[L]<=T<a[R] где a[N]=бесконечность
                      // реального обращения к a[N] нет.
                      while (R-L>1)
                      {
                         M=(R+L)/2;// если массивы не длиннее миллиарда элементов
                         if (T<a[M])
                         {
                             R=M;
                         }else //a[M]<=T
                         {
                             L=M;
                         }
                      }
                      lindex=L;
                      found=a[L]==T;
                        0
                        для массива длинной 2 и искомым элементом на 1й (не 0й) позиции работать не будет + все случаи которые сводятся к этому. видимо иногда полезней мыслить в человеческих терминах :)
                          0
                          Почему не будет? Изначально L=0, R=2. M будет выставлено равным 1. Поскольку этот элемент искомый, то T<a[1] не верно и мы получим L=M=1. В конце мы сравним a[1] и T и получим, что они совпадают как и положено. lindex будет равен L=1, как и требовалось.
                            0
                            ваша правда. будет. видимо сонный был :)
                          +1
                          Вы выбрали неудачный инвариант. В книге Вирта «Algorithms and Data Structures» www-old.oberon.ethz.ch/WirthPubl/AD.pdf (есть русский перевод www.ozon.ru/context/detail/id/4803785/ ) используется такой инвариант:
                          (Ak: 0 <= k < L: a[k] < T) & (Ak: R <= k < N: a[k] >= T)
                          Т.е., не a[L], а a[R] может быть равно T.
                          Тогда не требуется дополнительный анализ перед циклом:

                          L:=0;R:=N; 
                          WHILE L < R DO
                            m:=(L+R) DIV 2;
                            IF a[m] < T THEN
                              L := m+1
                            ELSE
                              R := m
                            END
                          END
                          
                          +1
                          1) обычно инвариант цикла определяется как условие верное перед каждой итерацией цикла.
                          «истинно перед циклом, истинно в процессе выполнения цикла и истинно при выходе из цикла» — вовсем непонятно, потому что можно подумать что условие верно всегда. но обычно инвариант цикла может нарушаться в теле, лишь бы он был верен перед очередной итерацией.
                          2) добавьте в статью пару слов о том что лучше бы еще чтоб инвариант гарантировал что цикл завершится. в идеале должна быть некая мера, которая должна уменьшаться с каждой итерацией цикла
                          3) перенесите в подходящий блог. статься полезна многим, а так ее почти никто не прочитает
                            0
                            Для тех кто заинтересовался можете почитать книжку Шеня «Программирование: теоремы и задачи», там про инвариант цикла рассказывается в самом начале, а дальше много чего еще интересного.
                              0
                              Еще есть старая советская книга Кушниренко, Лебедев «Программирование для математиков». По-моему там глава целая посвящена циклам и инвариантам

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

                            Самое читаемое