Module: 이진 검색


Problem

1/5

정렬된 배열에서 이진 검색: 시작(C++)

Theory Click to read/hide

<사업부>

이진 검색은 효율적인 — 복잡도 추정치는 O(log2(n))인 반면, 기존 순차 검색은 O(n)입니다. 즉, 예를 들어 1024개 요소의 배열에 대해 선형 검색은 최악의 경우 원하는 요소가 배열에 없을 때 모든 1024개 요소를 처리합니다. 이진 검색은 \(log_2(1024) = 10\) 요소를 처리하기에 충분합니다. 이 결과는 루프의 첫 번째 단계 이후 검색 영역이 512개 요소로 좁혀지고 두 번째 – 최대 256 등

이 알고리즘의 단점은 데이터 순서 지정에 대한 요구 사항과 일정한(데이터 양과 무관한) 시간에 모든 데이터 요소에 액세스할 수 있는 기능입니다. 따라서 이 알고리즘은 순서가 지정되지 않은 배열 및 연결된 목록을 기반으로 하는 모든 데이터 구조에서 작동할 수 없습니다.


구현
안녕 (오른쪽 – 왼쪽 > 1)  // 오른쪽 테두리가 왼쪽의 오른쪽에 있는 한
NC
  가운데 = (왼쪽 + 오른쪽) /< /span> 2; // 검색 영역의 중간
  if (A[middle] >= b) 그렇다면
    오른쪽 = 가운데; // 오른쪽 테두리 이동
  그렇지 않으면
    왼쪽 = 가운데; // 그렇지 않으면 왼쪽 테두리를 이동
참조
if (A[right] == X) then
  오른쪽 출력;
그렇지 않으면
  출력 -1;

위치:
A - 소스 배열,
N - 배열 크기,
X - 원하는 숫자.
 

Problem

이진 검색 알고리즘을 구현합니다.
 
데이터 입력
입력의 첫 번째 줄에는 자연수 N 및 K(\(0<N <= 100000,\ 0< K<=10^9\) ). 두 번째 줄에는 오름차순으로 정렬된 배열의 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!