Реализации алгоритмов/Двоичный поиск

C

#include <stdio.h>

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».
 */
#define FOUND(i)    makeResult(i, 1)
#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[n - 1] < x) {
        /* искомый элемент больше всех в массиве */
        return NOTFOUND(n);
    }

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

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

    /* Если условный оператор if (n == 0) и т.д. в начале опущен -
     * значит, тут раскомментировать!
     */
    if (/* last < n && */ a[last] == 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;
}

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# 7.0+

Цикл:

static (bool, int) BinarySearch <T> (T[] sorted_values, int value, bool descending = false) where T : IComparable
{
    int left = 0;
    for (int right = sorted_values.Length, middle; left < right; )
    {
        if (sorted_values[left].CompareTo(value) == 0)
            return (true, left)
        middle = left + (right - left) / 2;
        var c = sorted_values[middle].CompareTo(value);
        if (c == 0)
        {
            if (middle == left + 1)
                return (true, middle);
            right = middle + 1;
        }
        if ((c < 0) == descending)
            right = middle;
        else
            left = middle + 1;
    }
    return (false, left);
}

Рекурсия:

public static (bool, int) BinarySearch <T> (T[] sorted_values, int value, bool descending = false) where T : IComparable
{
    // Внутренняя рекурсивная функция
    (bool, int) SearchOnRange (int left, int right)
    {
        if (left >= right)
            return (False, left);
        if (sorted_values[left] == value)
            return (True, left);
        int middle = left + (right - left) / 2;
        if (sorted_values[middle] == value)
            return middle == left + 1
                ? (True, middle)
                : SearchOnRange(left, middle + 1);
        return (sorted_values[middle] < value) == descending
            ? SearchOnRange(left, middle)
            : SearchOnRange(middle + 1, right);
    }
    // Тело внешней нерекурсивной функции
    return SearchOnRange(0, sorted_values.Length());
}

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) >>> 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;
	}
	
}

PL/SQL

type sort_lst is table of integer; 
-----------------------------------------------------------
Function binary_search(in_sorted_list IN sort_lst, in_key in pls_integer, in_left in pls_integer, in_right in pls_integer)
 return pls_integer
  IS
    l_left pls_integer default in_sorted_list.first;
    l_right pls_integer default in_sorted_list.last;
    l_midkey pls_integer;
    overflow_exc exception;
    pragma exception_init(overflow_exc, -01426);
begin 
     If not ((in_left is null) or (in_right is null)) then -- если не первая итерация
        l_left:=in_left; l_right:=in_right; 
     end if;
      
        If (l_right-l_Left) = 1 then
            if in_key = in_sorted_list(l_right) then
               return in_key;
            else
               return null;--не нашли ключ
            end if;
         end if;
     
         l_midkey:=l_left+(l_right-l_left)/2;
         
         if in_key = in_sorted_list(l_midkey) then
            return in_key;
         elsif in_sorted_list(l_midkey)>in_key then
            return binary_search(in_sorted_list, in_key, l_left, l_midkey); 
         else 
            return binary_search(in_sorted_list => in_sorted_list,in_key =>  in_key,in_left  =>  l_midkey, in_right =>  l_right);
         end if;
     
exception
     when overflow_exc then
        raise;
end binary_search;

Python

Принимаются:

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

Возвращается: кортеж (tuple) из двух значений:

• логическое значение: True (если искомое значение присутствует в списке), либо False (если отсутствует).
• индекс найденного в списке значения, либо индекс, по которому можно вставить в список отсутствующее значение не нарушая упорядоченности его элементов.

Цикл:

def binary_search (sorted_values, value, descending=False):
    left = 0
    right = len(sorted_values)
    while left < right:
        if sorted_values[left] == value:
            return (True, left)
        middle = left + (right - left) // 2
        if sorted_values[middle] == value:
            if middle == left + 1:
                return (True, middle)
            right = middle + 1
        if (sorted_values[middle] < value) == descending:
            right = middle
        else:
            left = middle + 1
    return (False, left)

Рекурсия:

def binary_search (sorted_values, value, descending=False):
    def search_on_range (left, right):
        if left >= right:
            return (False, left)
        if sorted_values[left] == value:
            return (True, left) 
        middle = left + (right - left) // 2
        if sorted_values[middle] == value:
            if middle == left + 1:
                return (True, middle)
            else:
                return search_on_range(left, middle + 1)
        if (sorted_values[middle] < value) == descending:
            return search_on_range(left, middle)
        else:
            return search_on_range(middle + 1, right)
    return search_on_range(0, len(sorted_values))