Problem

1/5

بحث ثنائي في مصفوفة مرتبة: ابدأ (C ++)

Theory Click to read/hide

البحث الثنائي هو & mdash؛ تقدير درجة تعقيدها هو O (log2 (n)) ، بينما البحث المتسلسل التقليدي يحتوي على O (n) . هذا يعني أنه ، على سبيل المثال ، بالنسبة لمصفوفة من 1024 عنصرًا ، فإن البحث الخطي ، في أسوأ الحالات ، عندما لا يكون العنصر المطلوب في المصفوفة ، سيعالج جميع العناصر البالغ عددها 1024. البحث الثنائي كافٍ لمعالجة عناصر \ (log_2 (1024) = 10 \) . يتم تحقيق هذه النتيجة بسبب حقيقة أنه بعد الخطوة الأولى من الحلقة ، تضيق منطقة البحث إلى 512 عنصرًا ، بعد الثانية & ndash ؛ حتى 256 إلخ. تتمثل عيوب هذه الخوارزمية في الحاجة إلى ترتيب البيانات ، فضلاً عن القدرة على الوصول إلى أي عنصر بيانات في وقت ثابت (بغض النظر عن كمية البيانات). وبالتالي ، لا يمكن للخوارزمية أن تعمل على المصفوفات غير المرتبة وأي هياكل بيانات تعتمد على القوائم المرتبطة.



التنفيذ 
 وداعًا  (يمين & ndash؛ يسار  & gt؛   1 )  // طالما أن الحد الأيمن على يمين اليسار 
 nc 
  الأوسط  =  (يسار  +  يمين)  / < / span>  2 ؛  // وسط منطقة البحث 
   if  (A [middle]  & gt؛ =  ب)  ثم 
    يمين  =  mid؛  // تحريك الحد الأيمن 
   بخلاف ذلك 
    يسار  =  mid؛  // وبخلاف ذلك انقل الحد الأيسر 
 سم مكعب 
 if  (A [right]  ==  X)  ثم 
  الإخراج الصحيح
 بخلاف ذلك 
  الإخراج  - 1  ؛

حيث:
A - مصفوفة المصدر ،
N - حجم المصفوفة ،
X - الرقم المطلوب.
نبسب ؛

Problem

تنفيذ خوارزمية بحث ثنائية.
& nbsp؛
إدخال البيانات
يحتوي السطر الأول من الإدخال على أرقام طبيعية N و K ( \ (0 & lt؛ N & lt؛ = 100000، \ 0 & lt؛ K & lt ؛ = 10 ^ 9 \) ). يحتوي السطر الثاني على عناصر المصفوفة N ، مرتبة بترتيب تصاعدي. عناصر المصفوفة هي أعداد صحيحة ، كل منها لا يتجاوز 10 9 .
& nbsp؛
الإخراج
مطلوب من أجل & nbsp؛ K إخراج رقمه في المصفوفة في سطر منفصل ، إذا حدث هذا الرقم في المصفوفة ، و & quot؛ NO & quot؛ خلاف ذلك. نبسب ؛
أمثلة <الجسم>
# إدخال الإخراج
1
105
1 2 3 4 5 6 7 8 9 10 & nbsp؛
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!