tìm kiếm giá trị trước và sau trong danh sách dài được sắp xếp

Question

Cách nhanh nhất để tìm số (ví dụ 12.31) trong danh sách được sắp xếp dài và nhận giá trị trước và sau giá trị "tìm kiếm" của tôi khi chính xác giá trị không được tìm thấy (ví dụ 11.12 và 12.03 trong danh sách dưới đây)?
Rất cám ơn trước.

long_list = [10.11, 11.12, 13.03, 14.2 .. 12345.67] 

Answer 1

Các nhanh nhất có lẽ là sử dụng built-in hỗ trợ trong python. Ở đây tôi đang nghĩ về mô-đun bisect. Dưới đây tôi đang sử dụng một từ điển để nhanh chóng kiểm tra O (1) nếu một giá trị nằm trong danh sách; nếu không, bisect được sử dụng để tìm các giá trị nhỏ hơn và lớn hơn giá trị tìm kiếm.

#!/usr/bin/env python 

import bisect 

def find_lt(a, x): 
    'Find rightmost value less than x' 
    i = bisect.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.bisect_right(a, x) 
    if i != len(a): 
     return a[i] 
    raise ValueError 

# First create a test-list (49996 items) 
i=1.0 
R=[1.0] 
D={} 
while i < 10000: 
    i+=0.2 
    i=round(i,2) 
    D[i]=True 
    R.append(i) 

# Locate a value, in this case 100.3 which is not in the list 
x=100.3 
if D.has_key(x): 
    print "found", x 
else: 
    print find_lt(R, x) 
    print find_gt(R, x) 

Output cho x=100.3:

100.2 
100.4 

Answer 2

Nếu danh sách của bạn được sắp xếp như trong ví dụ của bạn, tôi giả sử tìm kiếm nhị phân sẽ nhanh nhất.

Answer 3

Tìm kiếm theo hàm mũ (tìm kiếm phi mã AKA) sẽ hoạt động tốt hơn tìm kiếm nhị phân thuần túy nếu danh sách rất dài. Ý tưởng là để quét về phía trước từ vị trí 0 trên các bước tăng cho đến khi câu trả lời được truyền vào thời điểm này một tìm kiếm nhị phân có thể được thực hiện đến phạm vi được tạo thành bởi hai bước cuối cùng. Nếu không tìm thấy phần tử thì nỗ lực cuối cùng sẽ trỏ đến các phần tử gần nhất.

Hãy xem Basic Techniques for information retrieval. Thuật toán mã giả được cung cấp và họ thảo luận về sự phức tạp của nó đối với tìm kiếm nhị phân.

Answer 4

li = [10.11, 11.12, 13.03, 14.2, 15.6, 15.8, 17.9, 12345.67] 

def searsh(x,li): 
    itli = iter(li) 
    a = itli.next() 
    if a==x: 
     return a 
    else: 
     while True: 
      b = itli.next() 
      if b==x: 
       return b 
      elif a<x<b: 
       return (a,b) 
      a = itli.next() 
      if a==x: 
       return a 
      elif b<x<a: 
       return (b,a) 


print searsh(13.5,li) 
print searsh(10.11,li) 
print searsh(50.3,li) 
print searsh(12345.67,li) 

kết quả

(13.03, 14.2) 
10.11 
(17.9, 12345.67) 
12345.67 

Ngoài ra:

def searsh(x,li): 
    a = li[0] 
    if a==x: 
     return a 
    else: 
     j = 0 
     while True: 
      j += 1 
      b = li[j] 
      if b==x: 
       return b 
      elif a<x<b: 
       return (a,b) 
      j += 1 
      a = li[j] 
      if a==x: 
       return a 
      elif b<x<a: 
       return (b,a)