Module: 二进制搜索


Problem

1/5

在有序数组中进行二分查找：开始 (C++)

Theory Click to read/hide

<分区>

二分查找是一种高效的 —其复杂度估计为 O(log2(n))，而传统的顺序搜索为 O(n)。这意味着，例如，对于一个包含 1024 个元素的数组，在最坏的情况下，当所需元素不在数组中时，线性搜索将处理所有 1024 个元素。二进制搜索足以处理 \(log_2(1024) = 10\) 元素。这个结果的实现是因为在循环的第一步之后，搜索区域缩小到 512 个元素，在第二步之后搜索区域缩小到 512 个元素。最多 256 等

该算法的缺点是需要数据排序，以及在恒定（与数据量无关）时间内访问任何数据元素的能力。因此，该算法不适用于无序数组和任何基于链表的数据结构。


实施
再见（右–左> 1） // 只要右边框在左边的右边
数控
  中间 =（左 + 右）/< /span> 2; // 搜索区域中间
  如果 (A[middle] >= b)那么
    右=中间； // 移动右边框
  否则
    左边 = 中间； // 否则移动左边框
抄送
如果（A[右] == X）那么
  正确的输出；
否则
  输出-1；

其中：
A - 源数组，
N - 数组大小，
X - 所需的数字。
 

Problem

实现二分查找算法。
 
输入数据 
输入的第一行包含自然数 N 和 K (\(0）。第二行包含数组的 N 元素，按升序排列。数组的元素都是整数，每个整数不超过109。
 
输出
 K 需要在单独的一行输出它在数组中的数字，如果这个数字出现在数组中，并且“NO”否则。
 
例子
<头> <日># <正文>

time 1000 ms
memory 32 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
输入 输出
1
105
1 2 3 4 5 6 7 8 9 10 
 5
Write the 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";
}

     

Program check result

To check the solution of the problem, you need to register or log in!