Реализации алгоритмов/Двоичный поиск
#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;
}
#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;
}
Цикл:
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());
}
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;
}
}
/// 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.
#Что искать?:
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";
}
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;
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
Принимаются:
- список значений, упорядоченных по возрастанию либо убыванию;
- искомое значение; его тип должен соответствовать типам элементов списка;
- необязательный параметр логического типа, указывающий, считается ли список отсортированным по возрастанию (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))
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
}
}