Двоичный поиск в упорядоченном массиве: Начало

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

Двоичный поиск является эффективным алгоритмом — его оценка сложности O(log2(n)), в то время как у обычного последовательного поиска O(n). Это значит, что например, для массива из 1024 элементов линейный поиск в худшем случае (когда искомого элемента нет в массиве) обработает все 1024 элемента, но бинарным поиском достаточно обработать log2(1024) = 10 элементов. Такой результат достигается за счет того, что после первого шага цикла область поиска сужается до 512 элементов, после второго – до 256 и т.д.

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

Реализация

while (right – left > 1) // Пока правая граница правее левой
{
  middle = (left + right) / 2; // Середина области поиска
  if (A[middle] >= b)
    right = middle; // Передвигаем правую границу
  else
    left = middle; // Иначе передвигаем левую границу
}
if (A[right] == X)
  cout << right;
else
  cout << -1;

где:
А - исходный массив,
N - размер массива,
X - искомое число,

Task

Реализуйте алгоритм бинарного поиска.

Входные данные

В первой строке входных данных содержатся натуральные числа N и K (0<N <= 100000, 0<K<=10⁹ ). Во второй строке задаются N элементов массива, отсортированного по возрастанию. Элементы массива - целые числа, каждое из которых по модулю не превосходит 10⁹

Выходные данные

Требуется для K вывести в отдельную строку его номер в массиве, если это число встречается в массиве, и "NO" в противном случае.

Ввод	Вывод
10 5 1 2 3 4 5 6 7 8 9 10	5

Python

Write a program below
#include <iostream> #include <cmath> #include <vector> #include <algorithm> using namespace std; int Search_Binary (vector<int> arr, int key) { int midd = 0, left =-1, right = arr.size();

int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, w, h, l, r, k, index; cin >> n >> k; vector<int> A(n); for (int i = 0; i < n; i++) { cin >> A[i]; } index = Search_Binary (A, k); if (index >= 0) cout << index+1; else cout << "NO"; }

Write a program below

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

int Search_Binary (vector<int> arr, int key)
{
	int  midd = 0, left =-1, right = arr.size();

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n, w, h, l, r, k, index;

	cin >> n >> k;

	vector<int> A(n);

	for (int i = 0; i < n; i++) {
		cin >> A[i];
	}

       index = Search_Binary (A, k);
 
	if (index >= 0) 
		cout << index+1;
	else
		cout << "NO";
}

Your last submission is saved in the editor window.

Results:

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

All results:

Education

My Account

About us

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

№ 2/6 Двоичный поиск в упорядоченном массиве: Начало

All results:

Education

My Account

About us