Module: Ikili arama


Problem

1/5

Sıralı dizide ikili arama: başlat (C++)

Theory Click to read/hide

İkili arama verimli bir — karmaşıklık tahmini O(log2(n)) iken geleneksel sıralı aramada O(n) bulunur. Bu, örneğin 1024 öğelik bir dizi için, en kötü durumda, istenen öğenin dizide olmadığı bir doğrusal aramanın 1024 öğenin tamamını işleyebileceği anlamına gelir. \(log_2(1024) = 10\) öğelerini işlemek için ikili arama yeterlidir. Bu sonuç, döngünün ilk adımından sonra arama alanının 512 öğeye, ikinci adımdan sonra 512 öğeye kadar daralması nedeniyle elde edilir. 256'ya kadar vs.

Bu algoritmanın dezavantajları, veri sıralama gereksinimi ve herhangi bir veri öğesine sabit (veri miktarından bağımsız) bir süre içinde erişebilme yeteneğidir. Bu nedenle, algoritma sırasız diziler ve bağlantılı listelere dayalı herhangi bir veri yapısı üzerinde çalışamaz.


Uygulama
güle güle (sağ – sol > 1)  // Sağ kenarlık solun sağında olduğu sürece
nc
  orta = (sol + sağ) /< /span> 2; // Arama alanının ortası
  eğer (A[middle] >= b) sonra
    sağ = orta; // Sağ kenarlığı taşıyın
  aksi takdirde
    sol = orta; // Aksi takdirde sol kenarlığı hareket ettirin
cc
if (A[right] == X) o zaman
  doğru çıktı;
aksi takdirde
  çıktı -1;

nerede:
A - kaynak dizisi,
N - dizi boyutu,
X - istenen sayı.
 

Problem

Bir ikili arama algoritması uygulayın.
 
Giriş verileri 
Girişin ilk satırı N ve K doğal sayılarını içerir (\(0<N <= 100000,\ 0< K< ;=10^9\) ). İkinci satır, dizinin artan düzende sıralanmış N öğelerini içerir. Dizinin öğeleri, her biri 109'u geçmeyen tam sayılardır.
 
Çıktı
 K'nin dizideki numarasını ayrı bir satıra vermesi gerekir, eğer bu sayı dizide geçiyorsa "NO" aksi halde.
 
Örnekler

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++
# Girdi Çıktı
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!