Tìm mục bên dưới tiếp theo trong danh sách được sắp xếp

Question

giả sử tôi có danh sách các Bản đồ được sắp xếp. Bây giờ tôi muốn lấy chỉ mục của mục bên dưới thấp hơn của một giá trị đã cho. Thông thường cho vòng lặp aprroach có độ phức tạp của O (n). Vì danh sách được sắp xếp nên phải có cách để lấy chỉ mục với O (log n).

O My (n) Cách tiếp cận:

index=0 
for i,value in enumerate(mylist): 
    if value>compareValue: 
     index=i-1 

Có datatype để giải quyết vấn đề trong đó O (log n)?

Trân Sebastian

Answer 1

Bạn có thể thực hiện tìm kiếm nhị phân trên một mảng/danh sách để có được những chỉ số của đối tượng bạn đang tìm kiếm và lấy chỉ số dưới nó để có được sự xâm nhập thấp (cho rằng có thực sự là một mục thấp hơn!).

Xem: Binary search (bisection) in Python

Hãy cẩn thận khi comparing floating point numbers cho bình đẳng!

Answer 2

Để trả lời một phần câu hỏi về kiểu dữ liệu: Theo nghĩa chung, kiểu dữ liệu thích hợp nhất cho việc tìm kiếm các thứ trong thời gian O (log n) (trong khi duy trì hiệu suất O (1) trên chèn và xóa!) . Bạn có thể tìm thấy mọi thứ trong đó bằng cách đưa ra một loạt các quyết định trái-phải, rất giống với cách bạn thực hiện tìm kiếm nhị phân trong danh sách tuyến tính nhưng (IMO) trực quan hơn một chút về khái niệm.

Điều đó nói rằng, từ những gì tôi biết về Python, cây nhị phân dường như không nằm trong thư viện chuẩn của ngôn ngữ. Đối với ứng dụng của bạn, có lẽ sẽ không có lợi ích gì khi bao gồm việc triển khai chỉ cho mục đích này. Cuối cùng, cả hai cây nhị phân và tìm kiếm nhị phân trong danh sách được sắp xếp sẽ cho phép bạn rút ngắn tìm kiếm theo một bước: Không cần phải tìm kiếm mục khóa và sau đó quay trở lại mục tiền nhiệm của nó. Thay vào đó, trên mọi bước so sánh, nếu bạn gặp phải giá trị khóa, hoạt động như thể nó quá lớn. Điều này sẽ làm cho tìm kiếm của bạn kết thúc trên giá trị nhỏ hơn tiếp theo. Thực hiện cẩn thận, điều này cũng có thể giúp với các vấn đề "gần như bằng dấu chấm động nổi" vấn đề được đề cập bởi bart.

Answer 3

Làm thế nào về bisect?

>>> import bisect 
>>> float_list = [1.0, 1.3, 2.3, 4.5] 
>>> i = bisect.bisect_left(float_list, 2.5) 
>>> index = i - 1 
>>> index 
2 

Bạn có thể phải xử lý các trường hợp của một giá trị tìm kiếm nhỏ hơn hoặc bằng giá trị thấp nhất/tận cùng bên trái trong danh sách riêng (index == -1 trong trường hợp này).

Tùy thuộc vào chỉ mục bạn muốn có trong trường hợp bình đẳng, bạn có thể phải sử dụng bisect_right để thay thế.

Answer 4

Sử dụng mô-đun bisect. Hàm

bisect.bisect_left(mylist, compareValue) 

trả về điểm chèn thích hợp cho mục trong danh sách để duy trì thứ tự được sắp xếp.

Answer 5

import bisect 

def next_lower_value(values_list, input_value): 
    index= bisect.bisect_left(values_list, input_value) 
    if index == 0: # there's not a "next lower value" 
     raise NotImplementedError # you must decide what to do here 
    else: 
     return values_list[index - 1] 

>>> l= [11, 15, 23, 28, 45, 63, 94] 
>>> next_lower_value(l, 64) 
63 
>>> next_lower_value(l, 63) 
45 
>>> next_lower_value(l, 1000) 
94 
>>> next_lower_value(l, 1) 
Traceback (most recent call last): 
    File "<pyshell#29>", line 1, in <module> 
    next_lower_value(l, 1) 
    File "<pyshell#26>", line 4, in next_lower_value 
    raise NotImplementedError # you must decide what to do here 
NotImplementedError 

Vì bạn yêu cầu index và không phải là giá trị thấp hơn tiếp theo, thay đổi chức năng next_lower_value trở index - 1 thay vì values_list[index - 1].

Answer 6

Nếu tôi đọc quyền này, mục bên dưới tiếp theo là mục đầu tiên trong danh sách nhỏ hơn hoặc bằng x. Các bisect documentation for searching sorted lists cho chức năng này:

def find_le(a, x): 
    'Find rightmost value less than or equal to x' 
    i = bisect_right(a, x) 
    if i: 
     return a[i-1] 
    raise ValueError