Реализации алгоритмов/Двоичный поиск: различия между версиями
Содержимое удалено Содержимое добавлено
Нет описания правки |
+C, C++, Java из Википедии |
||
Строка 1:
{{wikipedia|Двоичный поиск}}
== [[w:Си (язык программирования)|C]] ==
<source lang="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;
}
</source>
== [[w:C++|C++]] ==
<source lang="cpp">
#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;
}
</source>
== [[w:Java|Java]] ==
<source lang="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;
}
}
</source>
== [[w:PL/SQL|PL/SQL]] ==
| |||