Tìm kiếm nhị phân (binary search) Python tìm vị trí mục trong mảng đã sắp xếp. Nó chia danh sách thành hai nửa. Nếu giá trị chỉ định cao hơn số giữa, tìm kiếm tập trung vào bên phải danh sách. Ngược lại, tìm kiếm tìm số ở bên trái danh sách.
Làm thế nào tìm vị trí mục trong danh sách? Tìm kiếm nhị phân hỗ trợ bạn. Bằng cách dùng tìm kiếm nhị phân, bạn dễ dàng tìm vị trí phần tử trong mảng đã sắp xếp.
Máy tính giỏi tìm kiếm qua danh sách tìm mục cụ thể. Quy tắc máy tính dùng tìm mục trong danh sách gọi là thuật toán tìm kiếm (search algorithms). Một thuật toán Python phổ biến nhất là tìm kiếm nhị phân.
Trong hướng dẫn này, chúng ta thảo luận tìm kiếm nhị phân là gì và cách hoạt động. Chúng ta sẽ đi qua ví dụ tìm kiếm nhị phân trong Python để bạn học cách viết vào chương trình. Hãy bắt đầu!
Python Binary Search là gì?
Tìm kiếm nhị phân Python là thuật toán tìm vị trí phần tử trong mảng có thứ tự. Tìm kiếm nhị phân liên tục chia danh sách thành hai nửa. Sau đó, tìm kiếm so sánh giá trị cao hơn hay thấp hơn giá trị giữa trong danh sách.
Có hai cách thực hiện tìm kiếm nhị phân. Cả hai cách đặt con trỏ (pointers) dùng theo dõi vị trí cao nhất và thấp nhất tại thời điểm cụ thể trong mảng.
Cách đầu tiên là phương pháp lặp (iterative method). Trong cách này, tập câu lệnh lặp lại để xác định vị trí phần tử trong mảng. Trong Python, dùng vòng lặp while cho mục đích này.
Cách khác là phương pháp đệ quy (recursive method). Đây là nơi viết hàm tự gọi lại liên tục cho đến khi tìm thấy phần tử trong danh sách. Phương pháp đệ quy dùng cách chia để trị (divide and conquer) thảo luận trước và lặp lại quá trình tìm kiếm cho đến khi tìm thấy phần tử.
Binary Search Tree Python: Từng bước
Với tất cả lời nói về chia để trị và đệ quy, dễ bị mấtOriented cách tìm kiếm nhị phân hoạt động. Vì vậy, chúng ta sẽ trực tiếp vào ví dụ cách tìm kiếm nhị phân hoạt động. Xem danh sách sau:
| 7 | 9 | 14 | 22 | 34 |
Chúng ta sẽ tìm số "22" trong danh sách.
Đầu tiên, đặt hai con trỏ trong danh sách. Một con trỏ phản ánh giá trị cao nhất, con trỏ kia phản ánh giá trị thấp nhất:
| Low | High | |||
| 7 | 9 | 14 | 22 | 34 |
Bước tiếp theo tìm phần tử giữa mảng, là 14. Nếu giá trị này bằng giá trị tìm kiếm, giá trị đó nên trả về.
Trong trường hợp này, 14 không giống 22. Vì vậy, chương trình cần so sánh.
Chúng ta sẽ so sánh số tìm kiếm với phần tử giữa bên phải phần tử giữa hiện tại. Chỉ làm nếu số tìm kiếm lớn hơn số giữa. Ngược lại, so sánh với phần tử giữa bên trái phần tử giữa hiện tại.
Số 22 lớn hơn 14. Chương trình bắt đầu so sánh 22 với phần tử giữa bên phải phần tử giữa hiện tại (14). Trong trường hợp này, số đó là 22. Bằng số tìm kiếm.
| Low | Middle | High | ||
| 7 | 9 | 14 | 22 | 34 |
Chúng ta tìm thấy giá trị giữa. Chương trình giờ trả về vị trí chỉ mục của số đó. Trong trường hợp này, vị trí chỉ mục 22 là 3 (nhớ danh sách chỉ mục từ 0!).
Cách triển khai Binary Search trong Python
Hãy làm bẩn tay với mã Python. Chúng ta sẽ khám phá triển khai tìm kiếm nhị phân Python dùng cả hai cách thảo luận: lặp và đệ quy.
Tìm kiếm nhị phân lặp trong Python
Bắt đầu với phương pháp lặp. Đây là nơi lặp qua mỗi mục danh sách. Sau đó, tìm giá trị giữa danh sách. Tiếp tục cho đến khi tìm thấy giá trị tìm kiếm.
Hàm Binary Search
Bắt đầu định nghĩa hàm Python cho tìm kiếm nhị phân:
def findValue(numbers, number_to_find):
low = 0
high = len(numbers) - 1
while low <= high:
middle = low + (high - low) // 2
if numbers[middle] == number_to_find:
return middle
elif numbers[middle] < number_to_find:
low = middle + 1
else:
high = middle - 1
return -1
Hàm chấp nhận hai tham số: danh sách muốn tìm kiếm, và số muốn tìm trong danh sách.
Chúng ta khai báo hai biến Python lưu giá trị mặc định cho giá trị thấp nhất và cao nhất trong danh sách. low đặt 0, chỉ mục bắt đầu trong danh sách. high đặt độ dài danh sách trừ một (vì danh sách chỉ mục từ 0).
Bước tiếp theo khai báo vòng lặp while Python. Vòng lặp chạy khi phần tử thấp nhất nhỏ hơn hoặc bằng số cao nhất. Nghĩa là vòng lặp chỉ chạy nếu số chưa tìm thấy.
Sau đó, tính số giữa. Làm bằng cách trừ giá trị thấp từ cao. Sau đó tính modulo (phần dư) số đó chia 2. Rồi cộng modulo vào giá trị số thấp nhất.
Nếu số giữa trong danh sách giống số muốn tìm, trả về vị trí số đó.
Đặt "low" mới bằng một lớn hơn vị trí giữa. Xảy ra nếu số giữa nhỏ hơn số muốn tìm. Điều này di chuyển tìm kiếm xuống bên trái danh sách, như ví dụ hình ảnh trước.
Ngược lại, đặt "high" mới bằng một nhỏ hơn vị trí giữa. Di chuyển tìm kiếm sang bên phải danh sách.
Điều này lặp lại cho đến khi low bằng hoặc nhỏ hơn high. Nếu giá trị không tìm thấy, trả về -1. Chúng ta sẽ nói tại sao sau.
Thực thi tìm kiếm
Thêm mã sau cuối chương trình, bên ngoài hàm findValue:
numbers = [7, 9, 14, 22, 34]
number_to_find = 22
final = findValue(numbers, number_to_find)
if final == -1:
print("This item was not found in the list.")
else:
print("The number " + str(number_to_find) + " was found at index position " + str(final) + ".")
Chúng ta khai báo danh sách mục muốn tìm kiếm. Sau đó chỉ định số muốn tìm, là 22.
Tiếp theo, gọi hàm findValue() và truyền danh sách.
Đây là nơi -1 từ trước xuất hiện. Nếu số trả về hàm là -1, nghĩa là mục không tìm thấy trong danh sách. Lập trình viên thường dùng -1 trong tình huống này vì hàm tìm kiếm không trả về số âm.
Ngược lại, chương trình in thông báo cho vị trí chỉ mục giá trị đó.
Mã trả về:
The number 22 was found at index position 3.
Bây giờ biết số 22 xuất hiện tại vị trí chỉ mục 3.
Tìm kiếm nhị phân đệ quy trong Python
Chúng ta cũng dùng đệ quy thực hiện tìm kiếm nhị phân. Đây là nơi định nghĩa hàm tự gọi liên tục cho đến khi điều kiện — tìm thấy số — được đáp ứng.
Định nghĩa hàm đệ quy
Giống ví dụ trước, bắt đầu viết hàm thực hiện tìm kiếm nhị phân:
def findValue(numbers, number_to_find, low, high):
if high >= low:
middle = low + (high - low) // 2
if numbers[middle] == number_to_find:
return middle
elif numbers[middle] < number_to_find:
return findValue(numbers, number_to_find, middle + 1, high)
else:
return findValue(numbers, number_to_find, low, middle - 1)
else:
return -1
Mã hơi tương tự ví dụ trước.
Bắt đầu kiểm tra giá trị cao nhất lớn hơn hoặc bằng low. Nếu không, chương trình trả về -1. Ngược lại, bắt đầu thực hiện tìm kiếm nhị phân.
Tính số giữa dùng cách tương tự ví dụ trước. Trừ thấp từ cao. Tính modulo (phần dư) giá trị đó chia 2. Cuối cùng cộng số thấp.
Chúng ta viết câu lệnh if quyết định cách tìm kiếm nhị phân tiến triển:
- Nếu số giữa bằng số tìm, vị trí số đó trả về.
- Nếu số giữa nhỏ hơn số tìm, hàm findValue() gọi lại. Lần này, giá trị low đặt bằng một lớn hơn giá trị giữa.
- Nếu số giữa lớn hơn số tìm, hàm findValue() gọi. Giá trị "high" bằng một nhỏ hơn giá trị giữa.
Viết chương trình chính
Còn lại viết chương trình chính:
numbers = [7, 9, 14, 22, 34]
number_to_find = 22
final = findValue(numbers, number_to_find, 0, len(numbers) - 1)
if final == -1:
print("This item was not found in the list.")
else:
print("The number " + str(number_to_find) + " was found at index position " + str(final) + ".")
Chương trình chính giống ví dụ trước trừ một khác biệt. Chúng ta truyền hai tham số mới cho hàm findValue(): low và high.
Cần làm vậy vì thuật toán đệ quy, không thể gán giá trị đó trong hàm. Nếu gán trong hàm, giá trị sẽ reset mỗi lần hàm thực thi, phá vỡ thuật toán tìm kiếm.
Mã trả về:
The number 22 was found at index position 3.
Chúng ta nhận cùng kết quả trước. Trong ví dụ này, dùng chương trình đệ quy thay vì lặp để thực hiện tìm kiếm nhị phân.
Khi nào nên dùng Python Binary Search?
Tìm kiếm nhị phân là cách hiệu quả tìm kiếm qua danh sách số. Tìm kiếm này hiệu quả hơn tìm kiếm tuyến tính (linear search). Vì phương pháp nhị phân cắt giảm tìm kiếm còn một nửa ngay khi tìm thấy giữa danh sách đã sắp xếp.
Quan trọng lưu ý danh sách phải được sắp xếp số trước khi dùng tìm kiếm nhị phân. Trước khi thực hiện, đảm bảo số sắp xếp tăng dần.
Phân tích độ phức tạp Binary Search Python
Độ phức tạp tìm kiếm nhị phân là bao nhiêu? Câu hỏi hay.
Thuật toán tìm kiếm nhị phân có độ phức tạp trường hợp tốt nhất O(1). Xảy ra khi so sánh đầu tiên bằng mục tìm kiếm.
Độ phức tạp trung bình và xấu nhất cho tìm kiếm nhị phân là O(log n). Nghĩa là thời gian tìm kiếm tăng theo logarit tùy thuộc vào số mục cần tìm trong danh sách.
Kết luận
Tìm kiếm nhị phân là cách hiệu quả tìm vị trí chỉ mục giá trị trong danh sách.
Mỗi lần chạy tìm kiếm nhị phân, tìm kiếm chia danh sách thành hai phần. Tìm kiếm tập trung vào phía danh sách gần số tìm kiếm nhất.
Mỗi lần tìm kiếm chạy, số lượng số chương trình cần tìm kiếm giảm một nửa.
Để tìm hiểu thêm Python, đọc hướng dẫn How to Learn Python.