Двоичный поиск: различия между версиями

Материал из Поле цифровой дидактики
Следующая правка →
 
м 1 версия импортирована
(нет различий)

Версия от 20:55, 19 октября 2022

Файл:Binary Search Depiction.svg
Визуализация бинарного поиска по массиву. Искомое число — 7.

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

Частным случаем двоичного поиска является метод бисекции, который применяется для поиска корней заданной непрерывной функции на заданном отрезке.

Поиск элемента в отсортированном массиве

Шаблон:Викиучебник

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

Несмотря на то, что код достаточно прост, в нём есть несколько ловушек.

  • Код (first + last) / 2 ошибочен, если first и last по отдельности умещаются в свой тип, а first+last — нет<ref name="joshua">Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts are Broken Шаблон:Wayback // Joshua Bloch, Google Research; перевод — Почти во всех реализациях двоичного поиска и сортировки слиянием есть ошибка Шаблон:Wayback</ref>. Если теоретически возможны массивы столь большого размера, приходится идти на ухищрения:
    • Использовать код first + (last - first) / 2, который точно не приведёт к переполнениям, если имеем дело с неотрицательными целыми числами и first<last.
      • Если first и last — указатели или итераторы, такой код единственно правильный, поскольку не нарушает абстракцию (уже операция «указатель + указатель» некорректна). Разумеется, чтобы сохранялась сложность алгоритма, нужны быстрые операции «указатель+число → указатель», «указатель−указатель → число».
    • Если first и last — типы со знаком, провести расчёт в беззнаковом типе: ((unsigned)first + (unsigned)last) / 2. В Java сработает такой код: (first + last) >>> 1 (знаковое двоичное сложение совпадает с беззнаковым, Java гарантирует такое поведение даже при переполнении, и вся эта формула оперирует знаковыми числами как беззнаковыми).
    • Написать расчёт на ассемблере, с использованием флага переноса. Что-то наподобие add eax, b; rcr eax, 1. А вот длинные типы использовать нецелесообразно, first + (last - first) / 2 быстрее.
  • В двоичном поиске часты ошибки на единицу, и каждая такая ошибка превращается в зацикливание, пропуск или выход за пределы массива. Поэтому важно протестировать такие случаи: пустой массив (n=0), один элемент (n=1), ищем отсутствующее значение (слишком большое, слишком маленькое и где-то в середине), ищем первый и последний элемент.
  • Иногда требуется, чтобы, если x в цепочке существует в нескольких экземплярах, находило не любой, а обязательно первый (как вариант: последний; либо вообще не x, а следующий за ним элемент).<ref>В C++ std::lower_bound находит первое вхождение x, а std::upper_bound — элемент, следующий за x.</ref> Например, функция Шаблон:Cpp из C++ находит первый из равных, а Шаблон:Cpp — элемент, следующий за x. Если не найдено — оба возвращают место, куда вставить.

Учёный Йон Бентли утверждает, что 90 % студентов, разрабатывая двоичный поиск, забывают учесть какое-либо из этих требований. И даже в код, написанный самим Йоном и ходивший из книги в книгу, вкралась ошибка: код не стоек к переполнениям<ref name="joshua"/>.

Пример реализации на Java

int binarySearch(int[] arr, int key) {
    int low = 0;
    int high = arr.length - 1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        int midVal = arr[mid];

        if (midVal < key)
            low = mid + 1;
        else if (midVal > key)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1);  // key not found.
}

Приложения

Практические приложения метода двоичного поиска разнообразны:

  • Широкое распространение в информатике применительно к поиску в структурах данных. Например, поиск в массивах данных осуществляется по ключу, присвоенному каждому из элементов массива (в простейшем случае сам элемент является ключом).
  • Также его применяют в качестве численного метода для нахождения приближённого решения уравнений (см. Метод бисекции).
  • Метод используется для нахождения экстремума целевой функции и в этом случае является методом условной одномерной оптимизации. Когда функция имеет вещественный аргумент, найти решение с точностью до [math]\displaystyle{ \varepsilon }[/math] можно за время [math]\displaystyle{ \log_2 1 / \varepsilon }[/math]. Когда аргумент дискретен, и изначально лежит на отрезке длины N, поиск решения займёт [math]\displaystyle{ 1 + \log_2N }[/math] времени. Наконец, для поиска экстремума, скажем, для определённости минимума, на очередном шаге отбрасывается тот из концов рассматриваемого отрезка, значение в котором максимально.

См. также

Примечания

1 }} 
       | {{#switch: {{{1}}}
         | узкие = columns reflist-narrow
         | широкие = columns reflist-wide
         | #default = columns
         }}
       | {{#switch: {{{1}}}
         | 1 = 
         | 2 | 3 = columns
         | #default = columns reflist-narrow
         }}
       }}
     | columns
     }}
   }}" style="{{#if: 
   | column-width:{{{colwidth}}};
   | {{#if: 
     | {{#iferror: {{#ifexpr: {{{1}}} > 1 }}
       | {{#switch: {{{1}}}
         | узкие | широкие = 
         | #default = column-width:{{{1}}};
         }}
       }}
     }}
   }} list-style-type: {{#switch: 
   | upper-alpha
   | upper-roman
   | lower-alpha
   | lower-greek
   | lower-roman = {{{group}}}
   | #default = decimal
   }};">

<references group="" responsive="{{#if: 

 | 0
 | {{#if: 
   | {{#iferror: {{#expr: {{{1}}} > 1 }}
     | {{#switch: {{{1}}}
       | узкие | широкие = 1
       | #default = 0
       }}
     | {{#switch: {{{1}}}
       | 1 = 0
       | #default = 1
       }}
     }}
   | 1
   }}
}}"></references>

Ошибка скрипта: Модуля «Check for unknown parameters» не существует.

Литература

  • Шаблон:Source
  • {{#if:Амосов А. А., Дубинский Ю. А., Копченова Н. П.|Амосов А. А., Дубинский Ю. А., Копченова Н. П. }}{{#if: |{{#if: |[{{{ссылка часть}}} {{{часть}}}]| {{{часть}}}}} // }}{{#if:|[[:s:{{{викитека}}}|Вычислительные методы для инженеров]]|{{#if:|[{{{ссылка}}} Вычислительные методы для инженеров]|Вычислительные методы для инженеров}}}}{{#if:| = }}{{#if:| / {{{ответственный}}}.|{{#if:||.}}}}{{#if:Вычислительные методы для инженеров|{{#if:| {{#if:| = {{{оригинал2}}} }}{{#if:| / {{{ответственный2}}}.|{{#if:||.}}}}}}}}{{#if:| — .}}{{#switch:{{#if:М.|м}}{{#if:Мир|и}}{{#if:1998|г}}
 |миг= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=М.|М.}} }}: Мир, 1998.
 |ми= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=М.|М.}} }}: Мир.
 |мг= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=М.|М.}} }}, 1998.
 |иг= — Мир, 1998.
 |м= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=М.|М..}} }}
 |и= — Мир.
 |г= — 1998.

}}{{#if:| — {{{том как есть}}}.}}{{#if:| — Т. {{{том}}}.}}{{#if:| — Vol. {{{volume}}}.}}{{#if:| — B. {{{band}}}.}}{{#if:| — {{{страницы как есть}}}.}}{{#if:| — С. .}}{{#if:| — {{{страниц как есть}}}.}}{{#if:| — {{{страниц}}} с.}}{{#if:| — P. {{{pages}}}.}}{{#if:| — S. {{{seite}}}.}}{{#if:| —  p.}}{{#if:| —  s.}}{{#if:| — ({{{серия}}}).}}{{#if:| — Шаблон:Nobr}}{{#if:| — ISBN }}

  • {{#if:Бахвалов Н. С., Жидков Н. П., Кобельков Г. Г.|Бахвалов Н. С., Жидков Н. П., Кобельков Г. Г. }}{{#if: |{{#if: |[{{{ссылка часть}}} {{{часть}}}]| {{{часть}}}}} // }}{{#if:|[[:s:{{{викитека}}}|Численные методы]]|{{#if:|[ Численные методы]|Численные методы}}}}{{#if:| = }}{{#if:| / {{{ответственный}}}.|{{#if:||.}}}}{{#if:Численные методы|{{#if:| {{#if:| = {{{оригинал2}}} }}{{#if:| / {{{ответственный2}}}.|{{#if:||.}}}}}}}}{{#if:8-е изд| — 8-е изд.}}{{#switch:{{#if:М.|м}}{{#if:Лаборатория Базовых Знаний|и}}{{#if:2000|г}}
 |миг= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=М.|М.}} }}: Лаборатория Базовых Знаний, 2000.
 |ми= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=М.|М.}} }}: Лаборатория Базовых Знаний.
 |мг= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=М.|М.}} }}, 2000.
 |иг= — Лаборатория Базовых Знаний, 2000.
 |м= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=М.|М..}} }}
 |и= — Лаборатория Базовых Знаний.
 |г= — 2000.

}}{{#if:| — {{{том как есть}}}.}}{{#if:| — Т. {{{том}}}.}}{{#if:| — Vol. {{{volume}}}.}}{{#if:| — B. {{{band}}}.}}{{#if:| — {{{страницы как есть}}}.}}{{#if:| — С. .}}{{#if:| — {{{страниц как есть}}}.}}{{#if:| — {{{страниц}}} с.}}{{#if:| — P. {{{pages}}}.}}{{#if:| — S. {{{seite}}}.}}{{#if:| —  p.}}{{#if:| —  s.}}{{#if:| — ({{{серия}}}).}}{{#if:| — Шаблон:Nobr}}{{#if:| — ISBN }}

  • {{#if:Вирт Н.|Вирт Н. }}{{#if: |{{#if: |[{{{ссылка часть}}} ]| }} // }}{{#if:|[[:s:{{{викитека}}}|Алгоритмы + структуры данных = программы]]|{{#if:https://archive.org/details/libgen_852%7CАлгоритмы + структуры данных = программы|Алгоритмы + структуры данных = программы}}}}{{#if:| = }}{{#if:| / {{{ответственный}}}.|{{#if:||.}}}}{{#if:Алгоритмы + структуры данных = программы|{{#if:| {{#if:| = {{{оригинал2}}} }}{{#if:| / {{{ответственный2}}}.|{{#if:||.}}}}}}}}{{#if:| — {{{издание}}}.}}{{#switch:{{#if:М.|м}}{{#if:«Мир»|и}}{{#if:1985|г}}
 |миг= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=М.|М.}} }}: «Мир», 1985.
 |ми= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=М.|М.}} }}: «Мир».
 |мг= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=М.|М.}} }}, 1985.
 |иг= — «Мир», 1985.
 |м= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=М.|М..}} }}
 |и= — «Мир».
 |г= — 1985.

}}{{#if:| — {{{том как есть}}}.}}{{#if:| — Т. {{{том}}}.}}{{#if:| — Vol. {{{volume}}}.}}{{#if:| — B. {{{band}}}.}}{{#if:| — {{{страницы как есть}}}.}}{{#if:28| — С. 28.}}{{#if:| — {{{страниц как есть}}}.}}{{#if:| — {{{страниц}}} с.}}{{#if:| — P. {{{pages}}}.}}{{#if:| — S. {{{seite}}}.}}{{#if:| —  p.}}{{#if:| —  s.}}{{#if:| — ({{{серия}}}).}}{{#if:| — Шаблон:Nobr}}{{#if:| — ISBN }}

  • {{#if:Волков Е. А.|Волков Е. А. }}{{#if: |{{#if: |[{{{ссылка часть}}} {{{часть}}}]| {{{часть}}}}} // }}{{#if:|[[:s:{{{викитека}}}|Численные методы]]|{{#if:|[ Численные методы]|Численные методы}}}}{{#if:| = }}{{#if:| / {{{ответственный}}}.|{{#if:||.}}}}{{#if:Численные методы|{{#if:| {{#if:| = {{{оригинал2}}} }}{{#if:| / {{{ответственный2}}}.|{{#if:||.}}}}}}}}{{#if:| — .}}{{#switch:{{#if:М.|м}}{{#if:Физматлит|и}}{{#if:2003|г}}
 |миг= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=М.|М.}} }}: Физматлит, 2003.
 |ми= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=М.|М.}} }}: Физматлит.
 |мг= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=М.|М.}} }}, 2003.
 |иг= — Физматлит, 2003.
 |м= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=М.|М..}} }}
 |и= — Физматлит.
 |г= — 2003.

}}{{#if:| — {{{том как есть}}}.}}{{#if:| — Т. {{{том}}}.}}{{#if:| — Vol. {{{volume}}}.}}{{#if:| — B. {{{band}}}.}}{{#if:| — {{{страницы как есть}}}.}}{{#if:| — С. .}}{{#if:| — {{{страниц как есть}}}.}}{{#if:| — {{{страниц}}} с.}}{{#if:| — P. {{{pages}}}.}}{{#if:| — S. {{{seite}}}.}}{{#if:| —  p.}}{{#if:| —  s.}}{{#if:| — ({{{серия}}}).}}{{#if:| — Шаблон:Nobr}}{{#if:| — ISBN }}

  • {{#if:Гилл Ф., Мюррей У., Райт М.|Гилл Ф., Мюррей У., Райт М. }}{{#if: |{{#if: |[{{{ссылка часть}}} {{{часть}}}]| {{{часть}}}}} // }}{{#if:|[[:s:{{{викитека}}}|Практическая оптимизация. Пер. с англ]]|{{#if:|[ Практическая оптимизация. Пер. с англ]|Практическая оптимизация. Пер. с англ}}}}{{#if:| = }}{{#if:| / {{{ответственный}}}.|{{#if:||.}}}}{{#if:Практическая оптимизация. Пер. с англ|{{#if:| {{#if:| = {{{оригинал2}}} }}{{#if:| / {{{ответственный2}}}.|{{#if:||.}}}}}}}}{{#if:| — .}}{{#switch:{{#if:М.|м}}{{#if:Мир|и}}{{#if:1985|г}}
 |миг= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=М.|М.}} }}: Мир, 1985.
 |ми= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=М.|М.}} }}: Мир.
 |мг= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=М.|М.}} }}, 1985.
 |иг= — Мир, 1985.
 |м= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=М.|М..}} }}
 |и= — Мир.
 |г= — 1985.

}}{{#if:| — {{{том как есть}}}.}}{{#if:| — Т. {{{том}}}.}}{{#if:| — Vol. {{{volume}}}.}}{{#if:| — B. {{{band}}}.}}{{#if:| — {{{страницы как есть}}}.}}{{#if:| — С. .}}{{#if:| — {{{страниц как есть}}}.}}{{#if:| — {{{страниц}}} с.}}{{#if:| — P. {{{pages}}}.}}{{#if:| — S. {{{seite}}}.}}{{#if:| —  p.}}{{#if:| —  s.}}{{#if:| — ({{{серия}}}).}}{{#if:| — Шаблон:Nobr}}{{#if:| — ISBN }}

  • Шаблон:Книга:CLRS
  • {{#if:Корн Г., Корн Т.|Корн Г., Корн Т. }}{{#if: |{{#if: |[{{{ссылка часть}}} {{{часть}}}]| {{{часть}}}}} // }}{{#if:|[[:s:{{{викитека}}}|Справочник по математике для научных работников и инженеров]]|{{#if:|[ Справочник по математике для научных работников и инженеров]|Справочник по математике для научных работников и инженеров}}}}{{#if:| = }}{{#if:| / {{{ответственный}}}.|{{#if:||.}}}}{{#if:Справочник по математике для научных работников и инженеров|{{#if:| {{#if:| = {{{оригинал2}}} }}{{#if:| / {{{ответственный2}}}.|{{#if:||.}}}}}}}}{{#if:| — .}}{{#switch:{{#if:М.|м}}{{#if:Наука|и}}{{#if:1970|г}}
 |миг= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=М.|М.}} }}: Наука, 1970.
 |ми= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=М.|М.}} }}: Наука.
 |мг= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=М.|М.}} }}, 1970.
 |иг= — Наука, 1970.
 |м= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=М.|М..}} }}
 |и= — Наука.
 |г= — 1970.

}}{{#if:| — {{{том как есть}}}.}}{{#if:| — Т. {{{том}}}.}}{{#if:| — Vol. {{{volume}}}.}}{{#if:| — B. {{{band}}}.}}{{#if:| — {{{страницы как есть}}}.}}{{#if:575-576| — С. 575-576.}}{{#if:| — {{{страниц как есть}}}.}}{{#if:| — {{{страниц}}} с.}}{{#if:| — P. {{{pages}}}.}}{{#if:| — S. {{{seite}}}.}}{{#if:| —  p.}}{{#if:| —  s.}}{{#if:| — ({{{серия}}}).}}{{#if:| — Шаблон:Nobr}}{{#if:| — ISBN }}

  • {{#if:Коршунов Ю. М., Коршунов Ю. М.|Коршунов Ю. М., Коршунов Ю. М. }}{{#if: |{{#if: |[{{{ссылка часть}}} {{{часть}}}]| {{{часть}}}}} // }}{{#if:|[[:s:{{{викитека}}}|Математические основы кибернетики]]|{{#if:|[ Математические основы кибернетики]|Математические основы кибернетики}}}}{{#if:| = }}{{#if:| / {{{ответственный}}}.|{{#if:||.}}}}{{#if:Математические основы кибернетики|{{#if:| {{#if:| = {{{оригинал2}}} }}{{#if:| / {{{ответственный2}}}.|{{#if:||.}}}}}}}}{{#if:| — .}}{{#switch:{{#if:|м}}{{#if:Энергоатомиздат|и}}{{#if:1972|г}}
 |миг= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}: Энергоатомиздат, 1972.
 |ми= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}: Энергоатомиздат.
 |мг= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}, 1972.
 |иг= — Энергоатомиздат, 1972.
 |м= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}.}} }}
 |и= — Энергоатомиздат.
 |г= — 1972.

}}{{#if:| — {{{том как есть}}}.}}{{#if:| — Т. {{{том}}}.}}{{#if:| — Vol. {{{volume}}}.}}{{#if:| — B. {{{band}}}.}}{{#if:| — {{{страницы как есть}}}.}}{{#if:| — С. .}}{{#if:| — {{{страниц как есть}}}.}}{{#if:| — {{{страниц}}} с.}}{{#if:| — P. {{{pages}}}.}}{{#if:| — S. {{{seite}}}.}}{{#if:| —  p.}}{{#if:| —  s.}}{{#if:| — ({{{серия}}}).}}{{#if:| — Шаблон:Nobr}}{{#if:| — ISBN }}

  • {{#if:Максимов Ю. А., Филлиповская Е. А.|Максимов Ю. А., Филлиповская Е. А. }}{{#if: |{{#if: |[{{{ссылка часть}}} {{{часть}}}]| {{{часть}}}}} // }}{{#if:|[[:s:{{{викитека}}}|Алгоритмы решения задач нелинейного программирования]]|{{#if:|[ Алгоритмы решения задач нелинейного программирования]|Алгоритмы решения задач нелинейного программирования}}}}{{#if:| = }}{{#if:| / {{{ответственный}}}.|{{#if:||.}}}}{{#if:Алгоритмы решения задач нелинейного программирования|{{#if:| {{#if:| = {{{оригинал2}}} }}{{#if:| / {{{ответственный2}}}.|{{#if:||.}}}}}}}}{{#if:| — .}}{{#switch:{{#if:М.|м}}{{#if:МИФИ|и}}{{#if:1982|г}}
 |миг= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=М.|М.}} }}: МИФИ, 1982.
 |ми= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=М.|М.}} }}: МИФИ.
 |мг= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=М.|М.}} }}, 1982.
 |иг= — МИФИ, 1982.
 |м= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=М.|М..}} }}
 |и= — МИФИ.
 |г= — 1982.

}}{{#if:| — {{{том как есть}}}.}}{{#if:| — Т. {{{том}}}.}}{{#if:| — Vol. {{{volume}}}.}}{{#if:| — B. {{{band}}}.}}{{#if:| — {{{страницы как есть}}}.}}{{#if:| — С. .}}{{#if:| — {{{страниц как есть}}}.}}{{#if:| — {{{страниц}}} с.}}{{#if:| — P. {{{pages}}}.}}{{#if:| — S. {{{seite}}}.}}{{#if:| —  p.}}{{#if:| —  s.}}{{#if:| — ({{{серия}}}).}}{{#if:| — Шаблон:Nobr}}{{#if:| — ISBN }}

  • {{#if:Роберт Седжвик.|Роберт Седжвик. }}{{#if: |{{#if: |[{{{ссылка часть}}} {{{часть}}}]| {{{часть}}}}} // }}{{#if:|[[:s:{{{викитека}}}|Фундаментальные алгоритмы на C. Анализ/Структуры данных/Сортировка/Поиск]]|{{#if:|[{{{ссылка}}} Фундаментальные алгоритмы на C. Анализ/Структуры данных/Сортировка/Поиск]|Фундаментальные алгоритмы на C. Анализ/Структуры данных/Сортировка/Поиск}}}}{{#if:Algorithms in C. Fundamentals/Data Structures/Sorting/Searching| = Algorithms in C. Fundamentals/Data Structures/Sorting/Searching }}{{#if:| / {{{ответственный}}}.|{{#if:||.}}}}{{#if:Фундаментальные алгоритмы на C. Анализ/Структуры данных/Сортировка/Поиск|{{#if:| {{#if:| = {{{оригинал2}}} }}{{#if:| / {{{ответственный2}}}.|{{#if:||.}}}}}}}}{{#if:| — {{{издание}}}.}}{{#switch:{{#if:СПб.|м}}{{#if:ДиаСофтЮП|и}}{{#if:2003|г}}
 |миг= — {{#if:СПб.|{{#switch:СПб.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:СПб.|СПб.}} }}: ДиаСофтЮП, 2003.
 |ми= — {{#if:СПб.|{{#switch:СПб.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:СПб.|СПб.}} }}: ДиаСофтЮП.
 |мг= — {{#if:СПб.|{{#switch:СПб.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:СПб.|СПб.}} }}, 2003.
 |иг= — ДиаСофтЮП, 2003.
 |м= — {{#if:СПб.|{{#switch:СПб.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:СПб.|СПб..}} }}
 |и= — ДиаСофтЮП.
 |г= — 2003.

}}{{#if:| — {{{том как есть}}}.}}{{#if:| — Т. {{{том}}}.}}{{#if:| — Vol. {{{volume}}}.}}{{#if:| — B. {{{band}}}.}}{{#if:| — {{{страницы как есть}}}.}}{{#if:672| — С. 672.}}{{#if:| — {{{страниц как есть}}}.}}{{#if:| — {{{страниц}}} с.}}{{#if:| — P. {{{pages}}}.}}{{#if:| — S. {{{seite}}}.}}{{#if:| —  p.}}{{#if:| —  s.}}{{#if:| — ({{{серия}}}).}}{{#if:| — Шаблон:Nobr}}{{#if:5-93772-081-4| — ISBN 5-93772-081-4}}

Ссылки

Источник — http://digida.mgpu.ru/index.php?title=Двоичный_поиск&oldid=4665