रैखिक खोज और बाइनरी खोज के बीच क्या अंतर है?

Question

रैखिक खोज और बाइनरी खोज के बीच क्या अंतर है?

Answer 1

ए linear search बिना किसी कूद के एक सूची, एक आइटम को देखता है। जटिलता शर्तों में यह O(n) खोज है - सूची खोजने के लिए लिया गया समय सूची के समान दर पर बड़ा हो जाता है।

ए binary search तब होता है जब आप एक क्रमबद्ध सूची के बीच से शुरू करते हैं, और यह देखते हैं कि यह उस मूल्य से अधिक या उससे कम है जो आप खोज रहे हैं, यह निर्धारित करता है कि मूल्य सूची के पहले या दूसरे भाग में है या नहीं । उपन्यासकार के माध्यम से आधा रास्ते पर जाएं, और फिर से तुलना करें आदि। यह बहुत अधिक है कि मनुष्य आमतौर पर एक शब्दकोष में एक शब्द कैसे देखते हैं (हालांकि हम बेहतर हेरिस्टिक का उपयोग करते हैं, जाहिर है - यदि आप "बिल्ली" की तलाश में हैं तो आप नहीं "एम" पर शुरू करें)। जटिलता शर्तों में यह O(log n) खोज है - खोज संचालन की संख्या सूची की तुलना में अधिक धीरे-धीरे बढ़ती है, क्योंकि आप प्रत्येक ऑपरेशन के साथ "खोज स्थान" को रोक रहे हैं।

उदाहरण के तौर पर, मान लें कि आप अक्षरों की ए-जेड सूची में इंडेक्स की तलाश कर रहे थे (इंडेक्स 0-25; हम इंडेक्स 20 पर मूल्य की तलाश में हैं)।

एक रेखीय खोज पूछना होगा:

list[0] == 'U'? संख्या
list[1] == 'U'? संख्या
list[2] == 'U'? संख्या
list[3] == 'U'? संख्या
list[4] == 'U'? संख्या
list[5] == 'U'? संख्या
... list[20] == 'U'? हाँ। ख़त्म होना।

द्विआधारी खोज पूछना होगा:

'U' के साथ list[12] ('M') की तुलना करें: छोटे, आगे पर लग रहे हो। (रेंज = 13-25)
'यू' के साथ list[19] ('टी') की तुलना करें: छोटे, आगे देखो। (रेंज = 20-25)
'यू' के साथ list[22] ('डब्ल्यू') की तुलना करें: बड़ा, पहले देखें। (रेंज = 20-21)
'यू' के साथ list[20] ('यू') की तुलना करें: इसे मिला! ख़त्म होना।

दो तुलना:

• द्विआधारी खोज इनपुट डेटा क्रमबद्ध करना की आवश्यकता है; रैखिक खोज
• बाइनरी खोज को तुलना करने की आवश्यकता है; रैखिक खोज के लिए केवल समानता तुलना की आवश्यकता होती है
• बाइनरी खोज में जटिलता ओ (लॉग एन) है; रैखिक खोज में जटिलता ओ (एन) है जैसा कि पहले
• पर चर्चा की गई है बाइनरी खोज को डेटा तक यादृच्छिक पहुंच की आवश्यकता है; (- एक रेखीय खोज कर सकते हैं धारा मनमाने ढंग से आकार के डेटा इसका मतलब है कि यह बहुत महत्वपूर्ण हो सकता है) एक फोनबुक में अपनी राह तलाशने की दो अलग अलग तरीकों के रूप में यह की

Answer 2

Think रैखिक खोज केवल अनुक्रमिक अभिगम की आवश्यकता है।शुरुआत में एक रैखिक खोज शुरू हो रही है, जब तक आप जो खोज रहे हैं उसे प्राप्त न करने तक हर नाम पढ़ना। दूसरी ओर, एक बाइनरी खोज, जब आप पुस्तक (आमतौर पर बीच में) खोलते हैं, तो पृष्ठ के शीर्ष पर नाम देखें, और यह तय करें कि आप जिस नाम को ढूंढ रहे हैं वह आपके से बड़ा या छोटा है देख रहे हैं यदि आप जिस नाम की तलाश कर रहे हैं वह बड़ा है, तो आप इस शैली में पुस्तक के ऊपरी हिस्से को खोजना जारी रखते हैं।

Answer 3

मूल्यों की सूची की शुरुआत में एक रैखिक खोज शुरू होती है, और जिसके परिणामस्वरूप आप खोज रहे हैं उसके लिए 1 से 1 जांचता है।

एक द्विआधारी खोज एक क्रमबद्ध सरणी के बीच में शुरू होती है, और यह निर्धारित करती है कि आप किन पक्ष (यदि कोई है) जिस मूल्य को आप ढूंढ रहे हैं वह चालू है। सरणी के उस "आधा" को फिर उसी फैशन में फिर से खोजा जाता है, जिससे परिणामों को हर बार आधे से विभाजित किया जाता है।

Answer 4

मैं एक फर्क

जोड़ने के लिए के लिए रैखिक खोज मूल्यों हल हो करने की जरूरत नहीं करना चाहते हैं।

लेकिन बाइनरी खोज के लिए मान क्रमबद्ध क्रम में होना चाहिए।

Answer 5

रैखिक खोज को अनुक्रमिक खोज के रूप में भी जाना जाता है, यह देखने के लिए अनुक्रम में प्रत्येक तत्व को देखता है कि वांछित तत्व डेटा संरचना में मौजूद है या नहीं। जब डेटा की मात्रा कम होती है, तो यह खोज तेज़ी से होती है। यह आसान है लेकिन काम की आवश्यकता की मात्रा के अनुपात में आवश्यक काम है। तत्वों की संख्या को दोगुना करने के लिए वांछित तत्व मौजूद नहीं होने पर समय को दोगुना कर देगा।

बाइनरी खोज बड़ी सरणी के लिए कुशल है। इसमें हम मध्य तत्व की जांच करते हैं। अगर मूल्य बड़ा है जो हम खोज रहे हैं, तो पहले छमाही में देखें; अन्यथा, दूसरे छमाही में देखें। वांछित वस्तु मिलने तक इसे दोहराएं। तालिका को बाइनरी खोज के लिए क्रमबद्ध किया जाना चाहिए। यह प्रत्येक पुनरावृत्ति पर आधे डेटा को समाप्त करता है। यह लॉगरिदमिक है।

यदि हमारे पास खोज करने के लिए 1000 तत्व हैं, तो बाइनरी खोज में लगभग 10 कदम होते हैं, रैखिक खोज 1000 कदम होते हैं।

Answer 6

द्विआधारी खोज चलाता हे में (logn) समय जबकि रैखिक खोज में हे (एन) चलाता बार इस प्रकार द्विआधारी खोज बेहतर प्रदर्शन

Answer 7

के बारे में है कि क्या जल्दी द्विआधारी खोज की जीत लागत के लायक है विचार करना सुनिश्चित करें है सूची को क्रमबद्ध करने के लिए (बाइनरी खोज का उपयोग करने में सक्षम होने के लिए)। अर्थात। यदि आपके पास बहुत सारे सम्मिलित/हटाए गए संचालन हैं और केवल एक सामयिक खोज है तो बाइनरी खोज कुल मिलाकर रैखिक खोज से धीमी हो सकती है।

Answer 8

इसे आज़माएं: यादृच्छिक नाम "अंतिम नाम, प्रथम नाम" चुनें और इसे अपनी फोनबुक में देखें।

पहली बार: पुस्तक की शुरुआत से शुरू करें, जब तक आप इसे न ढूंढें, तब तक नाम पढ़ना शुरू करें, या फिर वह स्थान ढूंढें जहां यह वर्णानुक्रम से हुआ होगा और ध्यान दें कि यह वहां नहीं है।

दूसरी बार: आधे रास्ते बिंदु पर पुस्तक खोलें और पृष्ठ को देखें। खुद से पूछें, क्या यह व्यक्ति बाएं या दाएं होना चाहिए। जो भी यह है, वह 1/2 ले लो और इसके बीच में खोजें। इस प्रक्रिया को तब तक दोहराएं जब तक आप उस पृष्ठ को नहीं ढूंढ लेते जहां प्रवेश होना चाहिए और फिर या तो कॉलम पर एक ही प्रक्रिया लागू करें, या पहले पृष्ठ पर नामों के साथ रैखिक रूप से खोज करें।

दोनों विधियों का समय और रिपोर्ट वापस!

[भी विचार क्या दृष्टिकोण बेहतर है अगर आपके पास नामों की एक सूची है, पृथक नहीं किया ...]

Answer 9

एक रेखीय खोज एक सूची, एक समय में एक आइटम, कूद के बिना नीचे लग रहा है।जटिलता शर्तों में यह एक ओ (एन) खोज है - सूची खोजने के लिए लिया गया समय सूची के समान दर पर बड़ा हो जाता है।

एक बाइनरी खोज तब होती है जब आप एक क्रमबद्ध सूची के बीच से शुरू करते हैं, और देखें कि यह उस मूल्य से अधिक या उससे कम है, जो यह निर्धारित करता है कि मान पहले या दूसरे छमाही में है या नहीं सूची। उपन्यासकार के माध्यम से आधा रास्ते पर जाएं, और फिर से तुलना करें आदि। यह बहुत अधिक है कि मनुष्य आमतौर पर एक शब्दकोष में एक शब्द कैसे देखते हैं (हालांकि हम बेहतर हेरिस्टिक का उपयोग करते हैं, जाहिर है - यदि आप "बिल्ली" की तलाश में हैं तो आप नहीं "एम" पर शुरू करें)। जटिलता शर्तों में यह एक ओ (लॉग एन) खोज है - खोज संचालन की संख्या सूची की तुलना में अधिक धीरे-धीरे बढ़ती है, क्योंकि आप प्रत्येक ऑपरेशन के साथ "खोज स्थान" को रोक रहे हैं।

Answer 10

एक रैखिक खोज डेटा की सूची में प्रत्येक तत्व को देखकर काम करती है जब तक कि यह या तो लक्ष्य पाता है या अंत तक पहुंच जाता है। इसके परिणामस्वरूप किसी दिए गए सूची पर ओ (एन) प्रदर्शन होता है। एक बाइनरी खोज पूर्व शर्त के साथ आता है कि डेटा को सॉर्ट किया जाना चाहिए। हम इस जानकारी का लाभ उठा सकते हैं ताकि हमारे लक्ष्य को खोजने के लिए हमें आवश्यक वस्तुओं की संख्या कम हो सके। हम जानते हैं कि यदि हम डेटा में एक यादृच्छिक आइटम देखते हैं (चलो मध्य आइटम कहें) और वह आइटम हमारे लक्ष्य से बड़ा है, तो उस आइटम के दाईं ओर सभी आइटम हमारे लक्ष्य से भी अधिक होंगे। इसका मतलब है कि हमें केवल डेटा के बाएं भाग को देखने की आवश्यकता है। असल में, हर बार जब हम लक्ष्य और मिस की खोज करते हैं, तो हम शेष वस्तुओं में से आधे को खत्म कर सकते हैं। यह हमें एक अच्छा ओ (लॉग एन) समय जटिलता देता है।

बस याद रखें कि सॉर्टिंग डेटा, सबसे कुशल एल्गोरिदम के साथ भी, हमेशा रैखिक खोज से धीमा होगा (सबसे तेज़ सॉर्टिंग एल्गोरिदम ओ (एन * लॉग एन) हैं)। तो आपको बाद में एक बाइनरी खोज करने के लिए डेटा को कभी भी सॉर्ट नहीं करना चाहिए। लेकिन यदि आप कई खोज करेंगे (कम से कम ओ (लॉग एन) खोजें कहें), डेटा को सॉर्ट करना उचित हो सकता है ताकि आप बाइनरी खोज कर सकें। आप ऐसी स्थितियों में हैश टेबल जैसी अन्य डेटा संरचनाओं पर भी विचार कर सकते हैं।

Answer 11

Linear Search आइटम के माध्यम से तब तक दिखता है जब तक यह खोज मूल्य नहीं पाता।

क्षमता: O(n)

उदाहरण पायथन कोड:

test_list = [1, 3, 9, 11, 15, 19, 29] 
test_val1 = 25 
test_val2 = 15 

def linear_search(input_array, search_value): 
    index = 0 
    while (index < len(input_array)) and (input_array[index] < search_value): 
     index += 1 
    if index >= len(input_array) or input_array[index] != search_value: 
     return -1 

    return index 


print linear_search(test_list, test_val1) 
print linear_search(test_list, test_val2) 

Binary Search सरणी के बीच तत्व पाता है। जांचता है कि मध्य मूल्य खोज मूल्य से अधिक या कम है। यदि यह छोटा है, तो यह सरणी के बाईं तरफ हो जाता है और उस भाग के मध्य तत्व को पाता है। यदि यह अधिक है, तो सरणी का सही हिस्सा प्राप्त होता है। जब तक यह खोज मूल्य नहीं पाता तब तक यह ऑपरेशन को रोक देता है। या यदि सरणी में कोई मान नहीं है तो खोज खत्म हो जाती है।

क्षमता: O(logn)

उदाहरण पायथन कोड:

test_list = [1, 3, 9, 11, 15, 19, 29] 
test_val1 = 25 
test_val2 = 15 

def binary_search(input_array, value): 
    low = 0 
    high = len(input_array) - 1 
    while low <= high: 
     mid = (low + high)/2 
     if input_array[mid] == value: 
      return mid 
     elif input_array[mid] < value: 
      low = mid + 1 
     else: 
      high = mid - 1 

    return -1 


print binary_search(test_list, test_val1) 
print binary_search(test_list, test_val2) 

इसके अलावा, आप और रैखिक के बारे में कल्पना की जानकारी यहां दी गई बाइनरी खोजें देख सकते हैं: https://www.cs.usfca.edu/~galles/visualization/Search.html