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; // وسط ناحیه جستجو
  اگر (A[middle] >= ب) سپس
    سمت راست = middle; // حاشیه سمت راست را حرکت دهید
  در غیر این صورت
    چپ = وسط; // در غیر این صورت حاشیه سمت چپ را حرکت دهید
سی سی
اگر (A[right] == X) سپس
  خروجی درست؛
در غیر این صورت
  خروجی -1;

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

Problem

یک الگوریتم جستجوی دودویی را پیاده سازی کنید.
 
داده‌های ورودی 
خط اول ورودی شامل اعداد طبیعی N و K (\(0<N <= 100000,\ 0< K< ;=10^9\) ). خط دوم شامل عناصر N آرایه است که به ترتیب صعودی مرتب شده اند. عناصر آرایه اعداد صحیح هستند که هر کدام از 10 تجاوز نمی کند9.
 
خروجی
برای  K لازم است که عدد خود را در آرایه در یک خط جداگانه خروجی دهد، اگر این عدد در آرایه وجود دارد، و "NO" در غیر این صورت.
 
نمونه‌ها
<سر> <بدن>
# ورودی خروجی
1
105
1 2 3 4 5 6 7 8 9 10 
 5

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++
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!