पाइथन

Question

में बाइनरी खोज एल्गोरिदम मैं पाइथन में बाइनरी खोज को कार्यान्वित करने की कोशिश कर रहा हूं और इसे निम्नानुसार लिखा है। हालांकि, जब भी needle_element सरणी में सबसे बड़े तत्व से बड़ा होता है, तो मैं इसे रोक नहीं सकता।

क्या आप मदद कर सकते हैं? धन्यवाद।

def binary_search(array, needle_element): 
    mid = (len(array))/2 
    if not len(array): 
     raise "Error" 
    if needle_element == array[mid]: 
     return mid 
    elif needle_element > array[mid]: 
     return mid + binary_search(array[mid:],needle_element) 
    elif needle_element < array[mid]: 
     return binary_search(array[:mid],needle_element) 
    else: 
     raise "Error" 

Answer 1

मामले कि needle_element > array[mid], आप वर्तमान में array[mid:] पुनरावर्ती कॉल करने के लिए पारित में

। लेकिन आप जानते हैं कि array[mid] बहुत छोटा है, इसलिए आप इसके बजाय array[mid+1:] पास कर सकते हैं (और तदनुसार लौटाए गए इंडेक्स को समायोजित करें)।

यदि सुई सरणी में सभी तत्वों की तुलना में बड़ी है, तो ऐसा करने से अंततः आपको एक खाली सरणी मिल जाएगी, और एक त्रुटि अपेक्षित के रूप में उठाई जाएगी।

नोट: प्रत्येक बार उप-सरणी बनाना बड़े एरे के लिए खराब प्रदर्शन होगा। इसके बजाय सरणी की सीमाओं में गुजरना बेहतर है।

Answer 2

यदि आप बाइनरी खोज कर रहे हैं, तो मुझे लगता है कि सरणी को सॉर्ट किया गया है। यदि यह सत्य है तो आपको सरणी में अंतिम तत्व की तुलना needle_element पर करने में सक्षम होना चाहिए। जैसा कि ऑक्टोपस कहता है, यह खोज शुरू होने से पहले किया जा सकता है।

Answer 3

आप यह देखने के लिए जांच सकते हैं कि needle_element सभी शुरू करने से पहले सरणी की सीमाओं में है। यह इसे और अधिक कुशल बना देगा, क्योंकि आपको अंत तक पहुंचने के लिए कई कदम नहीं करना पड़ेगा।

if needle_element < array[0] or needle_element > array[-1]: 
    # do something, raise error perhaps? 

Answer 4

सरणी [मध्य:] हर बार जब आप इसे कॉल करते हैं तो एक नई सब-कॉपी बनाता है = धीमा। इसके अलावा आप रिकर्सन का उपयोग करते हैं, जो कि पाइथन में भी धीमा है।

आज़माएं:

def binarysearch(sequence, value): 
    lo, hi = 0, len(sequence) - 1 
    while lo <= hi: 
     mid = (lo + hi) // 2 
     if sequence[mid] < value: 
      lo = mid + 1 
     elif value < sequence[mid]: 
      hi = mid - 1 
     else: 
      return mid 
    return None 

Answer 5

यह जितना लासे वी Karlsen एक lower और upper अनुक्रमित के साथ काम करने के लिए बेहतर प्रश्न के लिए एक टिप्पणी में सुझाव दे रहा था होगा।

इस कोड होगा: एक बार आप छोटी संख्या (बाईं ओर से) पर पहुँच गए हैं

def binary_search(array, target): 
    lower = 0 
    upper = len(array) 
    while lower < upper: # use < instead of <= 
     x = lower + (upper - lower) // 2 
     val = array[x] 
     if target == val: 
      return x 
     elif target > val: 
      if lower == x: # these two are the actual lines 
       break  # you're looking for 
      lower = x 
     elif target < val: 
      upper = x 

• lower < upper बंद हो जाएगा
• if lower == x: break बंद हो जाएगा एक बार आप अधिक संख्या में पहुँच गए हैं (दाईं ओर से)

उदाहरण:

>>> binary_search([1,5,8,10], 5) # return 1 
1 
>>> binary_search([1,5,8,10], 0) # return None 
>>> binary_search([1,5,8,10], 15) # return None 

Answer 6

बिसेक्ट मॉड्यूल का उपयोग क्यों नहीं करें? यह आपको आवश्यक नौकरी करना चाहिए --- आपके लिए बनाए रखने और परीक्षण करने के लिए कम कोड।

Answer 7

के रूप में दूसरों सुझाव आप अपने एल्गोरिथ्म सुधार कर सकते हैं, लेकिन जाने क्यों यह काम नहीं करता पर पहले देखो:

क्योंकि अगर needle_element > array[mid], आप में तत्व mid शामिल कर रहे हैं आप एक चक्र में फँस कर रहे विभाजित सरणी जो आप अगली खोज करते हैं। तो यदि सुई सरणी में नहीं है, तो आप अंततः हमेशा के लिए लंबाई की एक सरणी खोज रहे होंगे।इसके बजाय array[mid+1:] पास करें (यह कानूनी है भले ही mid+1 मान्य अनुक्रमणिका नहीं है), और अंततः आप अपने फ़ंक्शन को लंबाई शून्य की सरणी के साथ कॉल करेंगे। तो len(array) == 0 का अर्थ है "नहीं मिला", कोई त्रुटि नहीं। इसे उचित तरीके से संभाल लें।

Answer 8

सभी उत्तरों ऊपर सही हैं, लेकिन मुझे लगता है कि यह मेरे कोड

def binary_search(number): 
numbers_list = range(20, 100) 
i = 0 
j = len(numbers_list) 
while i < j: 
    middle = int((i + j)/2) 
    if number > numbers_list[middle]: 
     i = middle + 1 
    else: 
     j = middle 
return 'the index is '+str(i) 

Answer 9

यह पुनरावर्ती का उपयोग करके सरणी में कुंजी के सूचकांक रिटर्न साझा करने के लिए मदद मिलेगी।

राउंड() एक फ़ंक्शन को पूर्णांक में फ्लोट रूपांतरित करता है और कोड को तेज़ी से बना देता है और अपेक्षित मामले [ओ (लॉगन)] पर जाता है।

A=[1,2,3,4,5,6,7,8,9,10] 
low = 0 
hi = len(A) 
v=3 
def BS(A,low,hi,v): 
    mid = round((hi+low)/2.0) 
    if v == mid: 
     print ("You have found dude!" + " " + "Index of v is ", A.index(v)) 
    elif v < mid: 
     print ("Item is smaller than mid") 
     hi = mid-1 
     BS(A,low,hi,v) 
    else : 
     print ("Item is greater than mid") 
     low = mid + 1 
     BS(A,low,hi,v) 
BS(A,low,hi,v) 

Answer 10

def binary_search(array, target): 
    low = 0 
    mid = len(array)/2 
    upper = len(array) 

    if len(array) == 1: 
     if array[0] == target: 
      print target 
      return array[0] 
     else: 
      return False 
    if target == array[mid]: 
     print array[mid] 
     return mid 
    else: 
     if mid > low: 
      arrayl = array[0:mid] 
      binary_search(arrayl, target) 

     if upper > mid: 
      arrayu = array[mid:len(array)] 
      binary_search(arrayu, target) 

if __name__ == "__main__": 
    a = [3,2,9,8,4,1,9,6,5,9,7] 
    binary_search(a,9) 

Answer 11

कम/ऊपरी अनुक्रमित बिना

यह भी करना चाहिए:

def exists_element(element, array): 
    if not array: 
     yield False 

    mid = len(array) // 2 
    if element == array[mid]: 
     yield True 
    elif element < array[mid]: 
     yield from exists_element(element, array[:mid]) 
    else: 
     yield from exists_element(element, array[mid + 1:]) 

Answer 12

यह एक पूंछ पुनरावर्ती समाधान है, मुझे लगता है कि यह आंशिक सरणियों प्रति बनाने की बजाय क्लीनर है और फिर ट्रैक रखने लौटने के लिए इंडेक्सों का:

def binarySearch(elem, arr): 
    # return the index at which elem lies, or return false 
    # if elem is not found 
    # pre: array must be sorted 
    return binarySearchHelper(elem, arr, 0, len(arr) - 1) 

def binarySearchHelper(elem, arr, start, end): 
    if start > end: 
     return False 
    mid = (start + end)//2 
    if arr[mid] == elem: 
     return mid 
    elif arr[mid] > elem: 
     # recurse to the left of mid 
     return binarySearchHelper(elem, arr, start, mid - 1) 
    else: 
     # recurse to the right of mid 
     return binarySearchHelper(elem, arr, mid + 1, end)