Module: Bir dizideki öğeler için doğrusal ve ikili arama


Problem

6/7

Ikili arama

Theory Click to read/hide

önce { -ms-user-select: yok; -moz-user-select: yok; -webkit-user-select: yok; kullanıcı seçimi: yok; }

İkili Arama
İkili (veya ikili) arama verimli bir arama algoritmasıdır ve doğrusal aramadan daha hızlıdır. Örneğin 1024 elemanlı bir dizi için en kötü durumda (istenen eleman dizide yokken) bir lineer arama 1024 elemanın tamamını işleyecektir fakat ikili arama ile 10 elemanı işlemek 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.
 
Böyle bir algoritmanın dezavantajları, veri sıralama gereksiniminin yanı sıra 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 dizilerde çalışamaz.
 
Algoritma
  1. Orta öğeyi A[c] seçin ve X ile karşılaştırın.
  2. Eğer X = A[c] ise bulundu (dur).
  3. Eğer X < A[c], ilk yarıda daha fazla arama yapın.
  4. Eğer X > A[c] ise, ikinci yarıya daha yakından bakın.
     
Uygulama
L = 0; R=N; // başlangıç ​​bölümü iken ( L < R - 1) { c = (Sol + Sağ) / 2; // ortasını bulduk if ( X < A[c] ) // segment sıkıştırma R=c; başka L = c; } eğer ( A[L] == X) cout

nerede:
A - kaynak dizisi,
N - dizi boyutu,
X - aranan numara,

Diğer uygulamalar mümkündür.
Örneğin, döngüden erken çıkış kullanmak L = 0; R = N - 1; iken (R >= L) { c = (Sol + Sağ) / 2; eğer ( X == A[c] ) { nX = c; kırmak; } eğer (X < A[c]) R = orta - 1; eğer (X > A[c]) L = orta + 1 ise; } eğer ( nX < 0) cout

Problem

Artan düzende sıralanan verilen dizide, ikili aramayı kullanarak X değerine eşit öğenin değerini bulmanız gerekir. X klavyeden girilir. Programı sorunu çözecek şekilde değiştirin Öğelerin numaralandırılması sıfırdan başlar. Böyle bir öğe yoksa, program Bulunamadı çıktısını vermelidir.

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

Teacher commentary

Insert the missing code snippets
C++
Write the program below 
#include<iostream> 
using namespace std; 
main() 
{	
  const int Nmax=1000; 	
  int A[Nmax], i, L, R, X, N, c;	 
  cin >> N; 
  for (i=0; i<N; i++) 
    cin >> A[i]; 
  cin >> X; 
  L = 0; R = N;       
  while ( L < R-1 )     
       cout << "A["<< L << "]=" << X; 
  else cout << "Not found"; 
}

     

Program check result

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