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

Материал из Викиучебника — открытых книг для открытого мира

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

Pascal[править]

/// Binary search function using Pascal
// Defining function
function binarySearch(arr: array of integer; toFind: integer): integer;
var
  first, last, mid: integer;
begin
  result := -1;
  // Checking our array for emptiness.
  if (arr = nil) or (length(arr) = 0) then Exit;
  first := 0;
  last := length(arr) - 1;
  // Running binary search
  while (first < last) do
  begin
    mid := first + (last - first) div 2;
    if arr[mid] >= 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 arr[last] = toFind then result := last;
end;

const
  a: array of integer = (1, 2, 3, 4, 5);  
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.

Perl[править]

#Что искать?:
my @search = qw{88 2 15 92 45 66 98 8 17 77};
#Где?:
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};

#Показать результаты поиска чисел в числовом ряду
print bin_search(\@seq, $_) for @search;

#алгоритм поиска
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";
}

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 3[править]

def binary_search(array, x, lower=0, higher=None):
    if lower < 0:
        raise ValueError('Должен быть положительным!')
    if higher is None:
        higher = len(array)
    while lower < higher:
        middle = (lower + higher) // 2
        if array[middle] < x:
            lower = middle + 1
        else: 
            higher = middle
    return lower

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

Swift[править]

import Foundation

//Бинарный поиск для массива, отсортированного по возрастанию. Возвращает индекс искомого элемента или 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 list[indexMid] == value{
                return indexMid
            }
            
            if value < list[indexMid]{
                indexMax = indexMid-1
            }
            else{
                indexMin = indexMid+1
            }
        }
    }
    return nil
}

let array = [2, 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 array[middle] == element {
            return element
        } else if array.count == 1 {
            return nil
        }
        
        if array[middle] < element {
            startIndex = middle + 1
        } else if array[middle] > element {
            endIndex = middle - 1
        }
        
        let subArray = Array(array[startIndex...endIndex])
        return binarySearchRecursion(element: element, in: subArray)
    } else {
        return nil
    }
}