Problem

6/7

جستجوی باینری

Theory Click to read/hide

جستجوی باینری
جستجوی باینری (یا باینری) یک الگوریتم جستجوی کارآمد است و سریعتر از جستجوی خطی است. به عنوان مثال، برای یک آرایه از 1024 عنصر، جستجوی خطی در بدترین حالت (زمانی که عنصر مورد نظر در آرایه نباشد) تمام 1024 عنصر را پردازش می کند، اما کافی است 10 عنصر را با جستجوی باینری پردازش کنید. این نتیجه به این دلیل به دست می‌آید که پس از مرحله اول حلقه، ناحیه جستجو به 512 عنصر کاهش می‌یابد، پس از – تا 256 و غیره.
 
معایب چنین الگوریتمی نیاز به ترتیب داده ها و همچنین امکان دسترسی به هر عنصر داده در یک زمان ثابت (مستقل از مقدار داده) است. بنابراین، الگوریتم نمی تواند روی آرایه های نامرتب کار کند.
 
الگوریتم
  1. عنصر میانی A[c] را انتخاب کنید و با X مقایسه کنید.
  2. اگر X = A[c] پیدا شد (توقف کنید).
  3. اگر X < A[c]، در نیمه اول بیشتر جستجو کنید.
  4. اگر X > A[c]، به نیمه دوم نگاه کنید.
     
اجرا
L = 0; R=N; // بخش اولیه در حالی که (L < R - 1) { c = (L + R) / 2; // وسط را پیدا کرد اگر (X < A[c] ) // فشرده سازی بخش R=c; دیگر L = c; } اگر (A[L] == X) cout << "الف» << L<< "]=" << ایکس؛ دیگر cout << "پیدا نشد";

جایی که:
A - آرایه منبع،
N - اندازه آرایه،
X - شماره جستجو شده،

پیاده سازی های دیگر امکان پذیر است.
به عنوان مثال، استفاده از یک خروج زودهنگام از حلقه L = 0; R = N - 1; در حالی که (R >= L) { c = (L + R) / 2; اگر (X == A[c]) { nX = c; زنگ تفريح؛ } اگر (X < A[c]) R = وسط - 1; اگر (X > A[c]) L = وسط + 1; } اگر (nX < 0) cout << "پیدا نشد"; دیگر cout << "الف» << nX<< "]=" << X;

Problem

در آرایه داده شده، که به ترتیب صعودی مرتب شده اند، باید با استفاده از جستجوی باینری، مقدار عنصر برابر با مقدار X را پیدا کنید. X از صفحه کلید وارد می شود. برنامه را طوری تغییر دهید که مشکل را حل کند شماره گذاری عناصر از صفر شروع می شود. اگر چنین عنصری وجود نداشته باشد، برنامه باید Not found را خروجی دهد.

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!