HỌC TIN CÙNG THỦ KHOA

Trong Python không cài đặt hàm tìm kiếm nhị phân để tìm chính xác vị trí của phần tử có giá trị bằng x trong một dãy đã được sắp xếp tăng dần. Tuy nhiên, trong Python đã cài đặt sẵn hàm bisect/bisect_right module bisect.py trong thư mục Python37/Lib để tìm ra vị trí để có thể chèn x sao cho sau khi chèn thì dãy vẫn được sắp xếp theo thứ tự tăng dần. Một số tình huống hàm bisect này sẽ có thể được dùng kèm với hàm insort_right để thực hiện việc chèn.

Sử dụng các hàm này bằng lời gọi from bisect import bisect

Ta có thể dùng hàm bisect/bisect_right để tìm ra vị trí chính xác của phần tử có giá trị bằng x trong một dãy đã được sắp xếp tăng dần bằng cách như sau:

Code:

from bisect import bisect

def binary_search(a, x, lo, hi):  
    pos = bisect(a, x, lo, hi) 
    if pos == -1:
        return -1
    elif a[pos - 1] != x:
        return -1
    else:
        return pos - 1
a = [2, 3, 5, 9]

print(binary_search([2, 3, 5, 9], 9, 0, len(a))) # hi = len(a)

Nguồn: https://www.it-swarm-vi.tech/vi/python/tim-kiem-nhi-phan-chia-doi-trong-python/958483430/