Двоичный поиск

Статья на основе материалов из Википедии

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

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

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

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

/*Пример кода на языке программирования Си для поиска элемента x в массиве an , отсортированного в возрастающем порядке:*/

  1. include

struct Result { size_t pos; int isFound; };

struct Result makeResult(size_t pos, int isFound) { struct Result r; r.pos = pos; r.isFound = isFound; return r; }

/* Макросы, означающие «найдено в позиции i» и «не найдено, если нужно * вставить со сдвигом, то в позицию i». */

  1. define FOUND(i) makeResult(i, 1)
  2. define NOTFOUND(i) makeResult(i, 0)

struct Result binarySearch(size_t n, int a[], int x) { /* Номер первого элемента в массиве */ size_t first = 0; /* Номер элемента в массиве, СЛЕДУЮЩЕГО ЗА последним */ size_t last = n;

/* Начальная проверка, которую, в принципе, можно опустить — но тогда см. ниже! */ if (n == 0) { /* массив пуст */ return NOTFOUND(0); } else if (a[0] > x) { /* искомый элемент меньше всех в массиве */ return NOTFOUND(0); } else if (a- 1 < x) { /* искомый элемент больше всех в массиве */ return NOTFOUND(n); }

/* Если просматриваемый участок непустой, first < last */ while (first < last) { size_t mid = first + (last - first) / 2;

if (x <= amid ) last = mid; else first = mid + 1; }

/* Если условный оператор if (n == 0) и т.д. в начале опущен - * значит, тут раскомментировать! */ if (/* last < n && */ alast == x) { /* Искомый элемент найден. last - искомый индекс */ return FOUND(last); } else { /* Искомый элемент не найден. Но если вам вдруг надо его * вставить со сдвигом, то его место - last. */ return NOTFOUND(last); } }

int main() { int a[] = { 1, 3, 5, 7, 9 }; struct Result r = binarySearch(5, a, 12); /* Вторая подстановка соответствует соглашениям Windows; на Unix %zu */ printf("%s at %Iu\n", r.isFound ? "Found" : "Not found", r.pos); return 0; }

  1. include
  2. include

using namespace std;

vector::const_iterator binarySearch(const vector& container, int element) { const vector::const_iterator endIt = end(container);

vector::const_iterator left = begin(container); vector::const_iterator right = endIt;

if (container.size() == 0 || container.front() > element || container.back() < element) { return endIt; }

while (distance(left, right) > 0) { const vector::const_iterator mid = left + distance(left, right) / 2;

if (element <= *mid) { right = mid; } else { left = mid + 1; } }

if (*right == element) { return right; }

return endIt; }

int main() { const vector vec = {0,1,2,3,4,5,6,7,8,9,10}; // отсортированный контейнер const int element = 8; // искомый элемент

auto foundIt = binarySearch(vec, element); if (foundIt != vec.end()) { cout << *foundIt << endl; } return 0; }

/* * Создайте консольное приложение и скопируйте этот исходный код в файл Program.cs. */

using System;

namespace ConsoleApplication1 { class Program { static void Main(string[] args) { int[] a = { 1, 3, 5, 7, 9 }; Console.WriteLine("Ищем -1: {0}", BinarySearch(a,-1)); Console.WriteLine("Ищем 3: {0}", BinarySearch(a, 3)); Console.WriteLine("Ищем 6: {0}", BinarySearch(a, 6)); Console.WriteLine("Ищем 9: {0}", BinarySearch(a, 9)); Console.WriteLine("Ищем 20: {0}", BinarySearch(a, 20)); Console.ReadLine(); }

///

/// Бинарный поиск в отсортированном массиве. /// /// Отсортированный по возрастанию массив типа int[] /// Искомый элемент. /// Возвращает индекс искомого элемента либо null, если элемент не найден. private static int? BinarySearch(int[] a, int x) { // Проверить, имеет ли смыл вообще выполнять поиск: // - если длина массива равна нулю - искать нечего; // - если искомый элемент меньше первого элемента массива, значит, его в массиве нет; // - если искомый элемент больше последнего элемента массива, значит, его в массиве нет. if ((a.Length == 0) || (x < a[0]) || (x > a- 1 )) return null;

// Приступить к поиску. // Номер первого элемента в массиве. int first = 0; // Номер элемента массива, СЛЕДУЮЩЕГО за последним int last = a.Length;

// Если просматриваемый участок не пуст, first < last while (first < last) { int mid = first + (last - first) / 2;

if (x <= amid ) last = mid; else first = mid + 1; }

// Теперь last может указывать на искомый элемент массива. if (alast == x) return last; else return null; } } }

package binarysearch;

/* В стандартной библиотеке Java уже имеется реализация двоичного поиска (который при этом может быть расширен через интерфейс Comparator). * Для объектных типов данных общий вид метода выглядит так: java.util.Arrays.binarySearch(Tarray, T value[, Comparator c ) */ public class BinarySearch { private double[] array; public BinarySearch(double[] array) { this.array = array; } // собственно алгоритм поиска public int find(double x) { int i = -1; if (this.array != null) { int low = 0, high = this.array.length, mid; while (low < high) { mid = (low + high)/2; // Можно заменить на: (low + high) >>> 1, чтоб не возникло переполнение целого if (x == this.arraymid ) { i = mid; break; } else { if (x < this.arraymid ) { high = mid; } else { low = mid + 1; } } } } return i; } public static void main(String[] args) { // тесты (необходимо включить опцию -enableassertions) BinarySearch bs = new BinarySearch(null); assert bs.find(7) == -1; bs = new BinarySearch(new double[0]); assert bs.find(7) == -1; bs = new BinarySearch(new double[]{7}); assert bs.find(7) == 0; assert bs.find(20) == -1; bs = new BinarySearch(new double[]{7, 20}); assert bs.find(-30) == -1; assert bs.find(7) == 0; assert bs.find(12) == -1; assert bs.find(20) == 1; assert bs.find(30) == -1; bs = new BinarySearch(new double[]{-16, -9, -5, 0, 3, 7, 12, 18, 20, 24, 30, 32, 38, 47, 50}); assert bs.find(-30) == -1; assert bs.find(-16) == 0; assert bs.find(7) == 5; assert bs.find(20) == 8; assert bs.find(24) == 9; assert bs.find(40) == -1; assert bs.find(50) == 14; assert bs.find(60) == -1; } }

  1. Что искать?:
my @search = qw{88 2 15 92 45 66 98 8 17 77};
  1. Где?:
my @seq = qw{2 4 8 10 11 12 13 14 17 18 20 21 22 23 26 27 31 32 33 34 37 43 44 45 49 51 52 54 57 60 61 63 64 66 67 68 70 75 76 79 80 81 82 83 86 89 92 96 97 98};
  1. Показать результаты поиска чисел в числовом ряду
print bin_search(\@seq, $_) for @search;
  1. алгоритм поиска
sub bin_search{ my ($lst, $x) = @_; #0й элемент - текущий индекс; -1 - мин; 1 - макс my @idx = (undef, $#{$lst}, 0); my $cnt = 0;

while($idx-1 <= $idx[1]){ $idx[0] = int(($idx-1 + $idx[1]) / 2); ++$cnt;

#Места с 0 считаются return("$x найден на $idx[0] месте за $cnt шагов\n") if($x == $lst->$idx[0 ]);

($x < $lst->$idx[0 ])? ($idx[1] = $idx[0] - 1): ($idx-1 = $idx[0] + 1); }

return "$x не найден\n"; }

def bin_search(lst, x): lower_bound = 0 upper_bound = len(lst) while lower_bound != upper_bound: compared_value = (lower_bound + upper_bound) // 2 # Целочисленный тип в Python имеет неограниченную длину if x == lstcompared_value : return compared_value elif x < lstcompared_value : upper_bound = compared_value else: lower_bound = compared_value + 1 return None # если цикл окончен, то значение не найденно

lst = sorted(for x in input('Введите массив: ').split() ) x = int(input('Введите искомый элемент: ')) print(bin_search(lst, x))

import UIKit

//Бинарный поиск для массива, отсортированного по возрастанию. Возвращает индекс искомого элемента или nil, если искомый элемент не найден. func binSearch (list: Int , value: Int) -> Int?{ if !list.isEmpty{ var indexMin = list.startIndex var indexMax = list.endIndex-1 while indexMin <= indexMax{ let indexMid = indexMin + (indexMax - indexMin)/2 if listindexMid == value{ return indexMid } if value < listindexMid { indexMax = indexMid-1 } else{ indexMin = indexMid+1 } } } return nil }

let array = 5, 8

binSearch(array, value: 0) //nil binSearch(array, value: 2) //0 binSearch(array, value: 4) //nil binSearch(array, value: 5) //1 binSearch(array, value: 6) //nil binSearch(array, value: 8) //2 binSearch(array, value: 9) //nil

// Бинарный поиск элемента в массиве через рекурсию на Swift 3 // Результат работы функции - найденый элемент или nil (в случае отсутствия элемента в массиве)

func binarySearchRecursion(element: Int, in array: Int ) -> Int? { var startIndex = 0 var endIndex = array.count - 1 let middle = Int((startIndex + endIndex) / 2) if !array.isEmpty { if arraymiddle == element { return element } else if array.count == 1 { return nil } if arraymiddle < element { startIndex = middle + 1 } else if arraymiddle > element { endIndex = middle - 1 } let subArray = Array(arraystartIndex...endIndex ) return binarySearchRecursion(element: element, in: subArray) } else { return nil } }

/// Binary search function using Pascal var a: array of integer = (1, 2, 3, 4, 5);

// Defining function function binarySearch(arr: array of integer; toFind: integer): integer; var first, last, mid: integer; begin // Checking our array for emptiness. if ((arr = nil) or (length(arr) = 0)) then result := -1 else begin first := 0; last := length(arr) - 1; // Running binary search while (first < last) do begin mid := first + ((last - first) div 2); if (arrmid >= toFind) then last := mid else first := mid + 1; end; // After the end of the loop, lastIndex can point to the search item. // Otherwise the element is missing in the array. if (arrlast = toFind) then result := last else result := -1; end; end;

begin // Let's try out our function: writeln(binarySearch(a, 3)); // Output is: 2 writeln(binarySearch(a, 1)); // Output is: 0 writeln(binarySearch(a, 2)); // Output is: 1 writeln(binarySearch(a, 5)); // Output is: 4 writeln(binarySearch(a, 9)); // Output is: -1 writeln(binarySearch(a, 0)); // Output is: -1 end.

//// Binary search function using F#

/// Defining function let binarySearch arr toFind = let mutable result = new System.Nullable() /// Checking our array for emptiness. if (not(isNull(arr)) && Array.length(arr) > 0) then let mutable first = 0; let mutable last = Array.length(arr) - 1 /// Running binary search while first < last do let mid = first + (last - first) / 2 if (arr.mid >= toFind) then last <- mid else first <- mid + 1 /// After the end of the loop, lastIndex can point to the search item. /// Otherwise the element is missing in the array. if (arr.last = toFind) then result <- new System.Nullable(last) result;

let main = /// Let's try out our function: let a = 1; 2; 3; 4; 5 | printfn "%A" (binarySearch a 4) // Output is: 3 printfn "%A" (binarySearch a 1) // Output is: 0 printfn "%A" (binarySearch a 2) // Output is: 1 printfn "%A" (binarySearch a 5) // Output is: 4 printfn "%A" (binarySearch a 0) // Output is: printfn "%A" (binarySearch a 9) // Output is: 0

---- Binary search function using Lua

--- Cause standart Lua has no length parameter for its pseudo-arrays, I've wrote this method local function countOf(arr) count = 0 for i, v in pairs(arr) do count = count + 1 end return count end

--- Binary search function local function binSearch(arr, toFind, length) result = nil -- Check whether the length parameter was passed to the method. -- If not - calculate it ourself, -- but then binary search loses its meaning, cause counting (O(N)) -- is similar to standart element-per-element search (O(N)) if (length == nil) then length = countOf(arr) end -- Checking our array for emptiness. if ((arr ~= nil) and (length > 0)) then -- Lua starts counting from 1(!!!). Argh first = 1 last = length -- Running binary search while (first < last) do mid = first + math.floor((last - first) / 2) if (arrmid >= toFind) then last = mid else first = mid + 1 end end -- After the end of the loop, lastIndex can point to the search item -- Otherwise the element is missing in our array if (arrlast == toFind) then result = last end end return result end

-- Let's try out our function: a = { 0, 1, 2, 3, 4 } print(binSearch(a, 3)) -- Output is: 4 print(binSearch(a, 0)) -- Output is: 1 print(binSearch(a, -1)) -- Output is: nil print(binSearch({}, 2)) -- Output is: nil

//// Binary search function using JavaScript

/// Defining function function binSearch(arr, toFind) { /// Checking our array for emptiness. if (!arr) return null; var first = 0; var last = arr.length - 1; /// Running binary search while (first < last) { var mid = first + Math.floor((last - first) / 2); if (arrmid >= toFind) last = mid; else first = mid + 1; } /// After the end of the loop, lastIndex can point to the search item. /// Otherwise the element is missing in the array. if (arrlast == toFind) return last; else return null; }

/// Let's try out our function: console.log(binSearch(2, 4 , 4 )); // Output is: 2 console.log(binSearch(2, 4 , 3 )); // Output is: null console.log(binSearch(2, 4 , 2 )); // Output is: 1 console.log(binSearch( , 1 )); // Output is: null console.log(binSearch("abcdef",'c')); // Output is: 2

;;; Binary search function using LISP ;;; А то статейка какая-то неполная вышла. Где языки-гиганты минувших лет? | Kir

;; Defining function (defun bin-search(arr find) (let ((lastIndex (- (list-length arr) 1)) (firstIndex 0) (resultIndex 0)) ;; Checking our list for emptiness. (if (null arr) ;; If list is empty then setting our result's value to NIL (setf resultIndex NIL) ;; Else running binary search (progn (loop while (< firstIndex lastIndex) do (let ((midIndex (+ firstIndex (floor (- lastIndex firstIndex) 2)))) (if (>= (nth midIndex arr) find) (setf lastIndex midIndex) (setf firstIndex (+ midIndex 1))))) ;; After the end of the loop, lastIndex can point to the search item. ;; Otherwise the element is missing in the list. (if (= (nth lastIndex arr) find) (setf resultIndex lastIndex) (setf resultIndex NIL)))) ;; Returning our result's value. resultIndex))

; Let's try out our function: (print (bin-search '(1 2 3 4 5) 4)) ; Output is: 3 (print (bin-search '(1 2 3 4 5) 1)) ; Output is: 0 (print (bin-search '(1 2 3 4 5) 0)) ; Output is: NIL (print (bin-search '(1 2 3 4 5) 6)) ; Output is: NIL (print (bin-search '( ) 1)) ; Output is: NIL

' Binary search function using VisualBasic

Module BinSearchModule

Defining function Function BinSearch(ByVal arr As Integer(), ByVal toFind As Integer) As Integer? Dim result As Integer? = Nothing Checking our array for emptiness. If (Not (IsNothing(arr)) And (arr.Length > 0)) Then Dim first = 0 Dim last = arr.Length - 1 Running binary search While (first < last) Dim mid = first + Math.Floor((last - first) / 2) If (arr(mid) >= toFind) Then last = mid Else first = mid + 1 End If End While After the end of the loop, lastIndex can point to the search item. Otherwise the element Is missing in the array. If (arr(last) = toFind) Then result = last End If End If Return result End Function

Sub Main() Let's try out our function: Dim a = New Integer() {1, 2, 4, 8} Console.WriteLine(BinSearch(a, 2)) ' Output is: 1 Console.WriteLine(BinSearch(a, 8)) ' Output is: 3 Console.WriteLine(BinSearch(a, 1)) ' Output is: 0 Console.WriteLine(BinSearch(a, 4)) ' Output is: 2 Console.WriteLine(BinSearch(a, 0)) ' Output is: Console.WriteLine(BinSearch(a, 9)) ' Output is: Console.ReadLine() End Sub

End Module

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

  • Что будет, если first и last по отдельности умещаются в свой тип, а first+last — нет?[1] Если теоретически возможны массивы столь большого размера, приходится идти на ухищрения:
    • Использовать код first + (last - first) / 2, который точно не приведёт к переполнениям (то и другое — неотрицательные целые числа).
      • Если first и last — указатели или итераторы, такой код единственно правильный. Преобразование в uintptr_t и дальнейший расчёт в этом типе нарушает абстракцию, и нет гарантии, что результат останется корректным указателем. Разумеется, чтобы сохранялась сложность алгоритма, нужны быстрые операции «итератор+число → итератор», «итератор−итератор → число».
    • Если first и last — типы со знаком, провести расчёт в беззнаковом типе: ((unsigned)first + (unsigned)last) / 2. В Java соответственно: (first + last) >>> 1.
    • Написать расчёт на ассемблере, с использованием флага переноса. Что-то наподобие add eax, b; rcr eax, 1. А вот длинные типы использовать нецелесообразно, first + (last - first) / 2 быстрее.
  • В двоичном поиске часты ошибки на единицу. Поэтому важно протестировать такие случаи: пустой массив (n=0), ищем отсутствующее значение (слишком большое, слишком маленькое и где-то в середине), ищем первый и последний элемент. Не выходит ли алгоритм за границы массива? Не зацикливается ли?
  • Иногда требуется, чтобы, если x в цепочке существует в нескольких экземплярах, находило не любой, а обязательно первый (как вариант: последний; либо вообще не x, а следующий за ним элемент).[2] Код на Си в такой ситуации находит первый из равных, более простой код на Си++ — какой попало.

Учёный Йон Бентли утверждает, что 90 % студентов, разрабатывая двоичный поиск, забывают учесть какое-либо из этих требований. И даже в код, написанный самим Йоном и ходивший из книги в книгу, вкралась ошибка: код не стоек к переполнениям[1].

Приложения

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

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

См. также

Примечания

  1. Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts are Broken // Joshua Bloch, Google Research; перевод — Почти во всех реализациях двоичного поиска и сортировки слиянием есть ошибка
  2. В C++ std::lower_bound находит первое вхождение x, а std::upper_bound — элемент, следующий за x.

Литература

  • Бахвалов Н. С., Жидков Н. П., Кобельков Г. Г. Численные методы — 8-е изд — М. : Лаборатория Базовых Знаний, 2000
  • Волков Е. А. Численные методы — М. : Физматлит, 2003
  • Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ — М. : Мир, 1985
  • Корн Г., Корн Т. Справочник по математике для научных работников и инженеров — М. : Наука, 1970 — 575-576
  • Коршунов Ю. М., Коршунов Ю. М. Математические основы кибернетики — |место М. : Энергоатомиздат, 1972
  • Максимов Ю. А., Филлиповская Е. А. Алгоритмы решения задач нелинейного программирования — М. : МИФИ, 1982

Ссылки