Module: द्विआधारी खोज


Problem

1/5

आदेशित सरणी में बाइनरी खोज: प्रारंभ करें (सी ++)

Theory Click to read/hide

<दिव>

बाइनरी खोज एक कुशल — इसकी जटिलता का अनुमान O(log2(n)) है, जबकि पारंपरिक अनुक्रमिक खोज में O(n) है। इसका मतलब है कि, उदाहरण के लिए, 1024 तत्वों की एक सरणी के लिए, एक रैखिक खोज, सबसे खराब स्थिति में, जब वांछित तत्व सरणी में नहीं है, तो सभी 1024 तत्वों को संसाधित करेगा। बाइनरी खोज \(log_2(1024) = 10\) तत्वों को संसाधित करने के लिए पर्याप्त है। यह परिणाम इस तथ्य के कारण प्राप्त होता है कि लूप के पहले चरण के बाद, खोज क्षेत्र 512 तत्वों तक सीमित हो जाता है, दूसरे - के बाद; 256 तक आदि।

इस एल्गोरिदम के नुकसान डेटा ऑर्डर करने की आवश्यकता है, साथ ही किसी भी डेटा तत्व को निरंतर (डेटा की मात्रा से स्वतंत्र) समय में एक्सेस करने की क्षमता है। इस प्रकार, एल्गोरिथ्म अनियंत्रित सरणियों और लिंक्ड सूचियों के आधार पर किसी भी डेटा संरचना पर काम नहीं कर सकता है।


कार्यान्वयन
का उपयोग करके उत्पन्न किया गया
<पूर्व शैली = "मार्जिन-बाएं: 0 पीएक्स; मार्जिन-दाएं: 0 पीएक्स"> अलविदा (दाएं - बाएं > 1) // जब तक दायां बॉर्डर बाईं ओर दाईं ओर है एनसी मध्य = (बाएं + दाएं) /< /span> 2; // खोज क्षेत्र के मध्य अगर (A[middle] >= b) तब दाएँ = बीच में; // दायां बॉर्डर ले जाएं अन्यथा बाएं = बीच में; // अन्यथा बायां बॉर्डर ले जाएं सीसी अगर (ए[दाएं] == एक्स) तो सही आउटपुट; अन्यथा आउटपुट -1;

कहा पे:
A - स्रोत सरणी,
N - सरणी आकार,
X - वांछित संख्या।
 

Problem

बाइनरी खोज एल्गोरिदम लागू करें।
 
इनपुट डेटा 
इनपुट की पहली पंक्ति में प्राकृत संख्याएँ N और K (\(0<N <= 100000,\ 0< के&एलटी;=10^9\) )। दूसरी पंक्ति में सरणी के N तत्व शामिल हैं, जो आरोही क्रम में क्रमबद्ध हैं। सरणी के तत्व पूर्णांक हैं, जिनमें से प्रत्येक 109 से अधिक नहीं है।
 
आउटपुट
 K के लिए इसकी संख्या को एक अलग लाइन पर सरणी में आउटपुट करना आवश्यक है, यदि यह संख्या सरणी में होती है, और "नहीं" अन्यथा।
 
उदाहरण
<टेबल क्लास = "टेबल-बॉर्डर्ड टेबल-लिस्ट-टेस्ट टेबल-एसएम टेबल-स्ट्राइप्ड"> <सिर> <वें># <वें>इनपुट <वें>आउटपुट <शरीर> 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!