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

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 08:45, 6 июня 2018.

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

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

Рис. 1. Схема бинарного поиска

Алгоритм может быть определен в рекурсивной и нерекурсивной формах. Количество шагов поиска определится как log2n↑, где n-количество элементов, ↑ — округление в большую сторону до ближайшего целого числа. На каждом шаге осуществляется поиск середины отрезка по формуле mid = (left — right)/2 Если искомый элемент равен элементу с индексом mid, поиск завершается. В случае если искомый элемент меньше элемента с индексом mid, на место mid перемещается правая граница рассматриваемого отрезка, в противном случае — левая граница.

Рис. 2. Бинарный поиск

Подготовка Перед началом поиска устанавливаем левую и правую границы массива:

left = 0, right = 19

Шаг 1 Ищем индекс середины массива (округляем в меньшую сторону):

mid = (19+0)/2=9
  • Сравниваем значение по этому индексу с искомым:
69 < 82
  • Сдвигаем левую границу:
left = mid = 9

Шаг 2 Ищем индекс середины массива (округляем в меньшую сторону):

mid = (9+19)/2=14
  • Сравниваем значение по этому индексу с искомым:
84 > 82
  • Сдвигаем правую границу:
right = mid = 14

Шаг 3 Ищем индекс середины массива (округляем в меньшую сторону):

mid = (9+14)/2=11
  • Сравниваем значение по этому индексу с искомым:
78 < 82
  • Сдвигаем левую границу:
left = mid = 11

Шаг 4 Ищем индекс середины массива (округляем в меньшую сторону):

mid = (11+14)/2=12
  • Сравниваем значение по этому индексу с искомым:
80 < 82
  • Сдвигаем левую границу:
left = mid = 12

Шаг 5 Ищем индекс середины массива (округляем в меньшую сторону):

mid = (12+14)/2=13
  • Сравниваем значение по этому индексу с искомым:
82 = 82

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

left = mid + 1 right = mid — 1

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

Rод программы на C++ (язык программирования)
#include <iostream>
#include <vector>

using namespace std;

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

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

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

    while (distance(left, right) > 0) {
        const vector<int>::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<int> 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;
}

Код на C#


/*
 * Создайте консольное приложение и скопируйте этот исходный код в файл 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();
        }

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

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

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

                if (x <= a[mid])
                    last = mid;
                else
                    first = mid + 1;
            }

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

Код на Java

package binarysearch;

/* В стандартной библиотеке Java уже имеется реализация двоичного поиска (который при этом может быть расширен через интерфейс Comparator).
 * Для объектных типов данных общий вид метода выглядит так: java.util.Arrays.binarySearch(T[] array, 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.array[mid]) {
					i = mid;
					break;
				} else {
					if (x < this.array[mid]) {
						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;
	}
	
}

Код на Python 3

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 == lst[compared_value]:
            return compared_value
        elif x < lst[compared_value]:
            upper_bound = compared_value
        else:
            lower_bound = compared_value + 1
    return None  # если цикл окончен, то значение не найденно

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

Код на JavaScript

//// 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 (arr[mid] >= 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 (arr[last] == toFind)
        return last;
    else return null;
}

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

Приложения

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

  • Широкое распространение в информатика|информатике применительно к поиску в структурах данных. Например, поиск в массивах данных осуществляется по ключ (указатель)|ключу, присвоенному каждому из элементов массива (в простейшем случае сам элемент является ключом).
  • Также его применяют в качестве численные методы|численного метода для нахождения приближённого решения уравнений (см. Метод бисекции).
  • Метод используется для нахождения экстремума целевая функция|целевой функции и в этом случае является оптимизация (математика)|методом условной одномерной оптимизации.

Источники

  1. Двоичный поиск//wikipedia. Дата обновления: 08.05.2018. URL: https://ru.wikipedia.org/wiki/Двоичный_поиск (дата обращения: 20.05.2018)
  2. Бинарный поиск//prog-cpp. URL: https://prog-cpp.ru/search-binary/ (дата обращения: 30.05.2018)

Ссылки