Tìm số nhỏ nhất lớn hơn số đã cho trong danh sách được sắp xếp

Question

Với danh sách số được sắp xếp, tôi cần tìm số nhỏ nhất lớn hơn số đã cho. Xem xét danh sách này:

---

arr=[1,2,3,5,7,11,101,131,151,181,191,313,353,373,383] 

Giả sử số lượng quy định là 320. Sau đó, phương pháp của tôi nên trở về 353 như 353 là số nhỏ nhất lớn hơn 320.

Tôi cố gắng để sử dụng một chút thay đổi hình thức tìm kiếm nhị phân; tuy nhiên khi thực hiện chương trình đi vào vòng lặp vô hạn.

---

def modBinarySearch(arr,x): 
    l=len(arr) 
    mid=l/2 
    if arr[mid]>=x and arr[mid-1]<x: 
     return arr[mid] 
    elif arr[mid]>x and arr[mid-1]>x: 
     modBinarySearch(arr[mid:l],x) 
    else: 
     modBinarySearch(arr[0:mid],x) 

N=int(raw_input()) 
arr=[1,2,3,5,7,11,101,131,151,181,191,313,353,373,383] 
print modBinarySearch(arr,N) 

Ai đó có thể chỉ ra những gì tôi đang làm sai?

Answer 1

Nếu arr [giữa] và arr [mid-1], cả hai đều lớn hơn số của bạn, bạn nên tìm kiếm trong arr [0: trung bình], không bạn nghĩ?

elif arr[mid]>x and arr[mid-1]>x: 
    modBinarySearch(arr[0:mid],x) 
else: 
    modBinarySearch(arr[mid:1],x) 

Answer 2

Nếu kích thước danh sách của bạn sẽ là 15, hãy bỏ tìm kiếm nhị phân hoàn toàn và sử dụng tìm kiếm tuần tự.

Bạn sẽ tìm thấy mã dễ viết hơn và, trừ khi bạn cần thực hiện hàng triệu lần mỗi giây, giải pháp tuần tự sẽ nhanh hơn đủ.

Nếu bạn do cần phải kết hợp với tìm kiếm nhị phân, bước đầu tiên của bạn phải thực sự trả lại kết quả của các cuộc gọi đệ quy.

Answer 3

Có một mô-đun chuẩn, bisect, mà thực hiện điều này đã:

In [49]: arr[bisect.bisect(arr, 320)] 
Out[49]: 353 

Tôi nghĩ rằng đây sẽ là đi đến phương pháp để tìm kiếm danh sách được sắp xếp. Có một vài số examples trong hướng dẫn sử dụng.

Như để thực hiện của bạn, có một số vấn đề:

1. đệ quy của bạn không xử lý mảng nhỏ một cách chính xác.
2. Việc cắt lát được thực hiện trong nhánh thứ hai là không chính xác.
3. Chức năng của bạn không trả lại bất cứ điều gì.
4. Vì arr là thứ tự tăng dần, arr[mid]>x and arr[mid-1]>x tương đương với arr[mid-1]>x, cho thấy bạn đã không viết những gì bạn có nghĩa là

Cuối cùng nhưng không kém, đệ quy và tất cả những gì cắt là hoàn toàn không cần thiết cho vấn đề này.

Answer 4

NẾU danh sách được sắp xếp:

x = range(20) 
N= 15 

for i in x: 
    if i>N: 
     print i 
     break 

Cung cấp 16.

Nếu sử dụng NumPy:

x = np.arange(20) 
N = 15 
x[x>15][0] 

Cung cấp 16.

Nếu bạn đang tìm kiếm việc triển khai dễ dàng, cho vấn đề cụ thể của bạn, hãy để tôi lấy lại điều đó.

Answer 5

def modBinarySearch(arr, n): 
    m = len(arr)/2 

    if arr[m] >= n and arr[m - 1] < n: 
     return arr[m] 
    elif arr[m] > n and arr[m - 1] > n: 
     return modBinarySearch(arr[:m], n) 
    else: 
     return modBinarySearch(arr[m:], n) 


arr = [1, 2, 3, 5, 7, 11, 101, 131, 151, 181, 191, 313, 353, 373, 383] 
n = 320 
print(modBinarySearch(arr, n)) 

Answer 6

 python 3.2 

    next(i for i in arr if i>320) 

Answer 7

Các bisect module là sự lựa chọn tốt nhất của bạn cho việc này:

from bisect import bisect_left, bisect_right 

arr=[1,2,3,5,7,11,101,131,151,181,191,313,353,373,383] 


def find_lt(a, x): 
    'Find rightmost value less than x' 
    i = bisect_left(a, x) 
    if i: 
     return a[i-1] 
    raise ValueError 

def find_gt(a, x): 
    'Find leftmost value greater than x' 
    i = bisect_right(a, x) 
    if i != len(a): 
     return a[i] 
    raise ValueError 

print find_lt(arr,320)   
print find_gt(arr,320) 

in

313 
353  

Answer 8

def modBinarySearch(arr,x): 
    l=len(arr) 
    mid=l/2 
    if arr[mid] >= x and arr[mid-1] < x: 
     return arr[mid] 
    elif arr[mid]>x and arr[mid-1]>x: 
     num = modBinarySearch(arr[0:mid],x) 
    else: 
     num = modBinarySearch(arr[mid:l],x) 
    return num 

N=int(raw_input('Enter a number: ')) 
arr=[1, 2, 3, 5, 7, 11, 101, 131, 151, 181, 191, 313, 353, 373, 383] 
print modBinarySearch(arr,N)