Tìm kiếm nhị phân (bisect) bằng Python

Ở đây chúng ta sẽ thấy đường phân giác trong Python. Đường phân giác được sử dụng để tìm kiếm nhị phân. Kỹ thuật tìm kiếm nhị phân được sử dụng để tìm các phần tử trong danh sách đã sắp xếp. Đường phân giác là một hàm thư viện.

Chúng ta sẽ thấy ba tác vụ khác nhau bằng cách sử dụng bisect trong Python.

Tìm lần xuất hiện đầu tiên của một phần tử

Bisect.bisect_left (a, x, lo =0, hi =len (a)) hàm này được sử dụng để trả về điểm chèn bên trái nhất của x trong danh sách đã sắp xếp. Hai tham số cuối cùng là tùy chọn trong trường hợp này. Hai thứ này được sử dụng để tìm kiếm trong danh sách phụ.

Ví dụ

from bisect import bisect_left
def BinSearch(a, x):
   i = bisect_left(a, x)
   if i != len(a) and a[i] == x:
      return i
   else:
      return -1
a = [2, 3, 4, 4, 5, 8, 12, 36, 36, 36, 85, 89, 96]
x = int(4)
pos = BinSearch(a, x)
if pos == -1:
   print(x, "is absent")
else:
   print("First occurrence of", x, "is at position", pos)

Đầu ra

First occurrence of 4 is at position 2

Tìm giá trị lớn nhất nhỏ hơn x

Sử dụng tùy chọn bisect_left, chúng ta có thể nhận được giá trị lớn hơn, nhỏ hơn giá trị x (key).

Ví dụ

from bisect import bisect_left
def BinSearch(a, x):
   i = bisect_left(a, x)
   if i :
      return i-1
   else:
      return -1
a = [2, 3, 4, 4, 5, 8, 12, 36, 36, 36, 85, 89, 96]
x = int(8)
pos = BinSearch(a, x)
if pos == -1:
   print(x, "is absent")
else:
   print("Larger value, smaller than", x, "is at position", pos)

Đầu ra

Larger value, smaller than 8 is at position 4

Tìm đúng lần xuất hiện nhiều nhất của x

Bisect.bisect_right (a, x, lo =0, hi =len (a)) hàm này được sử dụng để trả về điểm chèn gần đúng nhất của x trong danh sách đã sắp xếp. Hai tham số cuối cùng là tùy chọn trong trường hợp này. Hai thứ này được sử dụng để tìm kiếm trong danh sách phụ.

Ví dụ

from bisect import bisect_right
def BinSearch(a, x):
   i = bisect_right(a, x)
   if i != len(a) + 1 and a[i-1] == x:
      return i-1
   else:
      return -1
a = [2, 3, 4, 4, 5, 8, 12, 36, 36, 36, 85, 89, 96]
x = int(36)
pos = BinSearch(a, x)
if pos == -1:
   print(x, "is absent")
else:
   print("Right most occurrence of", x, "is at position", pos)

Đầu ra

Right most occurrence of 36 is at position 9