Làm cách nào để tìm chỉ mục mà tại đó một mục mới có thể được chèn vào danh sách được sắp xếp và giữ cho nó được sắp xếp?

Question

a = 132 

b = [0, 10, 30, 60, 100, 150, 210, 280, 340, 480, 530] 

Tôi muốn biết rằng a phải ở vị trí thứ 6 trong danh sách đặt hàng b.

Cách nhiệt tình nhất để làm như vậy là gì?

Answer 1

Sử dụng bisect. Nó không phải là API đẹp nhất, nhưng nó chính xác là những gì bạn cần.

Bạn sẽ muốn sử dụng bisect.bisect, trả về chính xác những gì bạn muốn.

Answer 2

bisect là một mô-đun trong Thư viện chuẩn Python hoàn hảo cho tác vụ này. Hàm bisect trong mô-đun bisect sẽ cung cấp cho bạn chỉ mục của điểm chèn cho giá trị.

Để tôi cho một ví dụ mã cho bisect

from bisect import bisect 
a = 132 
b = [0, 10, 30, 60, 100, 150, 210, 280, 340, 480, 530] 
print(bisect(b, a)) 

Kết quả sẽ là 5 vì danh sách này là 0-dựa, vì vậy trong thực tế, nó là vị trí thứ 6.

Điều bạn có thể biết là sử dụng kết quả cho số insert.

index = bisect(b, a) 
b.insert(index, a) 

hoặc không có các biến trung gian

b.insert(bisect(b, a), a) 

Bây giờ b sẽ [0, 10, 30, 60, 100, 132, 150, 210, 280, 340, 480, 530].

Answer 3

Có thêm mối quan ngại với trường hợp cạnh. Ví dụ, giả sử bạn muốn chọn các yếu tố trong nói trên b trong khoảng (a, c) và bạn chọn chúng bằng cách sử dụng

b[idx_a:idx_c] 

thì bạn cần phải suy nghĩ về trường hợp a, c thực sự yếu tố của b. Lưu ý rằng

bisect.bisect(b, 10) 
bisect.bisect(b, 11) 

sẽ cung cấp cho cả hai chỉ số 2. Vì vậy, nếu a=10 chúng ta cần phải hạ thấp chỉ số bằng 1. May mắn thay, có một chức năng bisect.bisect_left mà thực hiện chính xác này, ví dụ, trong ví dụ của chúng tôi

bisect.bisect_left(b, 10) 

cung cấp cho 1.

Nhìn chung, chỉ mục bên trái phải được tính bằng cách sử dụng bisect.bisect_left() và chỉ mục bên phải bisect.bisect_right() (tương tự như bisect.bisect()).