Thuật toán tìm kiếm nhị phân trong python

Question

Tôi đang cố triển khai tìm kiếm nhị phân trong python và đã viết nó như sau. Tuy nhiên, tôi không thể làm cho nó dừng lại bất cứ khi nào needle_element lớn hơn phần tử lớn nhất trong mảng.

Bạn có thể trợ giúp không? Cảm ơn.

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

Trong trường hợp needle_element > array[mid], bạn hiện đang chuyển array[mid:] đến cuộc gọi đệ quy. Nhưng bạn biết rằng array[mid] quá nhỏ, vì vậy bạn có thể vượt qua array[mid+1:] thay thế (và điều chỉnh chỉ mục trả về tương ứng).

Nếu kim lớn hơn tất cả các phần tử trong mảng, thực hiện theo cách này cuối cùng sẽ cung cấp cho bạn một mảng trống và lỗi sẽ được tăng lên như mong đợi.

Lưu ý: Việc tạo một mảng phụ mỗi lần sẽ dẫn đến hiệu suất kém cho các mảng lớn. Tốt hơn là nên vượt qua giới hạn của mảng thay thế.

Answer 2

Nếu bạn đang thực hiện tìm kiếm nhị phân, tôi đoán mảng được sắp xếp. Nếu điều đó đúng, bạn có thể so sánh phần tử cuối cùng trong mảng với needle_element. Như bạch tuộc nói, điều này có thể được thực hiện trước khi bắt đầu tìm kiếm.

Answer 3

Bạn chỉ có thể kiểm tra để thấy rằng needle_element nằm trong giới hạn của mảng trước khi bắt đầu. Điều này sẽ làm cho nó hiệu quả hơn, vì bạn sẽ không phải thực hiện một số bước để có được đến cùng.

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

Answer 4

mảng [giữa:] tạo một bản sao con mới mỗi khi bạn gọi nó = chậm. Ngoài ra bạn sử dụng đệ quy, trong Python cũng chậm.

Hãy thử điều này:

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

Sẽ tốt hơn nhiều để làm việc với một lower và upper chỉ số như Lasse V. Karlsen được gợi ý trong một chú thích cho câu hỏi.

Đây sẽ là các mã:

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 sẽ ngừng khi bạn đã vượt quá số lượng nhỏ hơn (từ phía bên trái)
• if lower == x: break sẽ ngừng khi bạn đã vượt quá số lượng cao hơn (từ bên phải)

Ví dụ:

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

Tại sao không sử dụng mô-đun bisect? Nó sẽ làm công việc bạn cần --- ít mã hơn cho bạn để duy trì và kiểm tra.

Answer 7

Bạn có thể cải thiện thuật toán của bạn như những người khác đề nghị, nhưng trước tiên hãy xem lý do tại sao nó không hoạt động:

Bạn đang bị mắc kẹt trong một vòng lặp bởi vì nếu needle_element > array[mid], bạn bao gồm cả yếu tố mid trong mảng được chia đôi mà bạn tìm kiếm tiếp theo. Vì vậy, nếu kim không có trong mảng, bạn cuối cùng sẽ tìm kiếm một mảng dài một mãi mãi.Thay vào đó, hãy chuyển array[mid+1:] (nó hợp pháp ngay cả khi mid+1 không phải là chỉ mục hợp lệ) và cuối cùng bạn sẽ gọi hàm của mình với một mảng có độ dài bằng không. Vì vậy, len(array) == 0 có nghĩa là "không tìm thấy", không phải là lỗi. Xử lý nó một cách thích hợp.

Answer 8

Tất cả các câu trả lời ở trên là đúng sự thật, nhưng tôi nghĩ rằng nó sẽ giúp chia sẻ mã của tôi

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

Nó trả về chỉ số của chìa khóa trong mảng bằng cách sử dụng đệ quy.

vòng() là một hàm chuyển đổi float thành số nguyên và tạo mã nhanh và chuyển sang trường hợp dự kiến ​​[O (logn)].

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

Nếu không có/chỉ số trên thấp hơn này cũng nên làm:

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

Đây là một giải pháp đệ quy đuôi, tôi nghĩ rằng đây là sạch hơn vì sao chép mảng một phần và sau đó theo dõi trong số các chỉ mục trả lại:

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)