Thuật toán bisect (chia đôi) dùng để tìm vị trí trong list, nơi dữ liệu có thể được chèn để giữ list ở trạng thái đã sắp xếp. Python có module bisect. Sử dụng module này, ta có thể dùng các thuật toán bisect.
Để dùng module này, nên nhập bằng:
import bisect
Có một số thao tác liên quan đến bisect:
Phương thức bisect.bisect(list, element, begin, end)
Tìm vị trí trong list đã sắp xếp, nơi số có thể đặt và list vẫn giữ được thứ tự sắp xếp. Nếu phần tử đã có mặt, nó trả về vị trí bên phải nhất (rightmost) nơi số có thể chèn.
Phương thức bisect.bisect_left(list, element, begin, end)
Giống hệt bisect(). Chỉ khác: nếu mục đã có mặt, phương thức này trả về vị trí bên trái nhất (leftmost) để chèn dữ liệu.
Phương thức bisect.bisect_right(list, element, begin, end)
Hoàn toàn giống bisect().
Phương thức bisect.insort(list, element, begin, end)
Dùng để có list đã sắp xếp sau khi chèn phần tử vào vị trí đúng. Nếu phần tử đã có mặt, nó chèn ở vị trí bên phải nhất để giữ list sắp xếp.
Phương thức bisect.insort_left(list, element, begin, end)
Giống insort(). Chỉ khác: nếu phần tử đã có mặt, chèn ở vị trí bên trái nhất.
Phương thức bisect.insort_right(list, element, begin, end)
Hoàn toàn giống insort().
Mã ví dụ
import bisect
my_list = [11, 25, 36, 47, 56, 69, 69, 69, 78, 78, 91, 102, 120]
print('Vị trí đúng chèn 53: ' + str(bisect.bisect(my_list, 53, 0, len(my_list))))
print('Vị trí phải chèn 69: ' + str(bisect.bisect_right(my_list, 69, 0, len(my_list))))
print('Vị trí trái chèn 69: ' + str(bisect.bisect_left(my_list, 69, 0, len(my_list))))
bisect.insort(my_list, 59, 0, len(my_list))
print(my_list)
bisect.insort_left(my_list, 78, 0, len(my_list))
print(my_list)
Kết quả
Vị trí đúng chèn 53: 4 Vị trí phải chèn 69: 8 Vị trí trái chèn 69: 5 [11, 25, 36, 47, 56, 59, 69, 69, 69, 78, 78, 91, 102, 120] [11, 25, 36, 47, 56, 59, 69, 69, 69, 78, 78, 78, 91, 102, 120]