Module: 二分探索


Problem

1/5

順序付き配列の二分探索: start (C++)

Theory Click to read/hide

二分検索は効率的な検索です。その複雑さの推定値は O(log2(n)) ですが、従来の逐次検索は O(n) です。これは、たとえば 1024 個の要素の配列の場合、最悪の場合、目的の要素が配列内にない場合、線形検索は 1024 個の要素すべてを処理することを意味します。 \(log_2(1024) = 10\) 要素を処理するには、二分探索で十分です。この結果は、ループの最初のステップの後、2 番目のステップの後、検索範囲が 512 要素に絞り込まれるという事実によって達成されます。最大 256 など

このアルゴリズムの欠点は、データの順序付けが必要であることと、(データ量に関係なく) 一定時間内に任意のデータ要素にアクセスできることです。したがって、このアルゴリズムは、順序付けされていない配列やリンク リストに基づくデータ構造では機能しません。


実装
さようなら (右 – 左 > 1)  // 右境界線が左境界線の右側にある限り
ノースカロライナ
  中央 = (左 + 右) /< /span>2; // 検索エリアの中央
  if (A[middle] >= b) then
    右=中央; // 右の境界線を移動
  そうでない場合
    左=中央; // それ以外の場合は、左の境界線を移動します
cc
場合 (A[right] == X) その後
  正しい出力。
そうでない場合
  出力-1;

ここで:
A - ソース配列
N - 配列サイズ
X - 目的の数値。
 

Problem

二分探索アルゴリズムを実装します。
 
入力データ 
入力の最初の行には、自然数 N と K (\(0<N <= 100000,\ 0< K< ;=10^9\) )。 2 行目には、配列の N 要素が含まれており、昇順で並べ替えられています。配列の要素は整数で、それぞれが 109 を超えません。
 
出力
 K は、この番号が配列内にある場合、配列内のその番号を別の行に出力する必要があります。そうでなければ。
 
例
<頭> <本体>

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!