Thuật toán Python

Tìm kiếm nhị phân trong Python

Tìm một giá trị trong list một triệu phần tử đã sắp xếp chỉ với khoảng 20 bước, nhờ chia đôi phạm vi tìm sau mỗi lần so sánh.

  • Trung cấp
  • Đọc trong 2 phút
  • 1 ví dụ chạy được
Bạn sẽ học được gì
  • Các chỉ số low, middle và high
  • Vì sao list phải được sắp xếp
  • Module bisect
Tìm 17 trong [3, 8, 12, 17, 25, 31]
3low
8
12middle ✗
17✓ chỉ số 3
25
31high
17 > 12 nên bỏ nửa trái; phần tử giữa tiếp theo chính là 17.

Mỗi bước bỏ đi một nửa

Vấn đề

Tìm một giá trị trong list một triệu phần tử bằng cách xem từng phần tử có thể mất tới một triệu lần so sánh. Khi list đã được sắp xếp, bạn có cách nhanh hơn nhiều: chừng 20 lần so sánh là đủ, vì mỗi lần kiểm tra loại được một nửa phần còn lại.

Hình dung đời thường

Tìm kiếm nhị phân (binary search) chính là cách bạn tra một từ trong cuốn từ điển giấy. Bạn mở ở giữa, xem từ cần tìm đứng trước hay sau trang đó, rồi bỏ đi nửa không thể chứa nó. Lặp lại với nửa còn lại cho tới khi gặp đúng từ.

Từ cuốn từ điển giấy đến code
low, high = 0, len(values) - 1📖 Những trang còn phải tìm
middle = (low + high) // 2👆 Mở ở giữa
low = middle + 1➡️ Từ cần tìm nằm sau: bỏ nửa đầu
high = middle - 1⬅️ Từ cần tìm nằm trước: bỏ nửa sau
Mỗi lần so sánh bỏ đi một nửa, nên list khổng lồ cũng chỉ cần ít bước.
Định nghĩa ngắn gọn

Tìm kiếm nhị phân tìm một giá trị trong list đã sắp xếp bằng cách liên tục so nó với phần tử ở giữa và bỏ đi nửa không thể chứa nó, mất khoảng O(log n) bước.

Những điểm quan trọng

  1. low và high đánh dấu phần list vẫn còn có thể chứa giá trị cần tìm.
  2. middle = (low + high) // 2 chọn vị trí ở giữa phần đó.
  3. Nếu values[middle] < target, giá trị cần tìm nằm bên phải nên low = middle + 1; ngược lại high = middle - 1.
  4. while low <= high: dừng khi khoảng tìm kiếm rỗng, và hàm trả về -1 nghĩa là không tìm thấy.
  5. Với 17, quá trình tìm xem 12, rồi 25, rồi 17: ba lần so sánh thay vì bốn.

Khi nào nên sử dụng?

  • Tìm trong dữ liệu lớn đã sắp xếp: mã số, từ điển, log đã sắp theo thời gian.
  • Tìm vị trí chèn một giá trị để list vẫn giữ thứ tự.
  • Trò chơi đoán số và mọi bài toán có thể thu hẹp đáp án bằng cách hỏi cao hơn hay thấp hơn.

Khi nào chưa cần

  • Dữ liệu chưa sắp xếp: sắp xếp chỉ để tìm một lần còn tốn hơn tìm tuần tự.
  • List nhỏ hoặc chỉ tìm một lần: in hay dictionary đơn giản hơn; tra cứu theo khóa nhiều lần thì dict hoặc set còn nhanh hơn.

Mô phỏng Tìm kiếm nhị phân (binary search) trong Python

O(log n)

Nhấn Phát hoặc Từng bước để theo dõi từng phép so sánh và thay đổi dữ liệu.

Code ví dụ

Chạy code →
main.py
def binary_search(values, target):
    low, high = 0, len(values) - 1
    while low <= high:
        middle = (low + high) // 2
        if values[middle] == target:
            return middle
        if values[middle] < target:
            low = middle + 1
        else:
            high = middle - 1
    return -1

print(binary_search([3, 8, 12, 17, 25, 31], 17))
Lấy nút Run cho ví dụ này

Kết quả khi chạy

3

Giải thích code

Hai biến low và high xác định phạm vi tìm kiếm còn lại. Nếu phần tử ở giữa nhỏ hơn giá trị cần tìm, thuật toán bỏ nửa bên trái bằng cách đặt low = middle + 1, ngược lại thì bỏ nửa bên phải. Độ phức tạp thời gian là O(log n), với điều kiện danh sách đầu vào bắt buộc phải được sắp xếp trước.

Thay đổi giá trị và chạy chương trình bằng trình chạy Python online của CodeUtility mà không cần cài Python.

Bài tập mở rộng

Hãy thử chỉnh sửa code theo các gợi ý dưới đây. Tự thay đổi và quan sát kết quả sẽ giúp bạn hiểu bài sâu hơn nhiều so với chỉ đọc code.

  1. Thử với danh sách rỗng, danh sách chỉ có một phần tử hoặc có giá trị trùng lặp.
  2. In ra trạng thái sau mỗi bước để quan sát thuật toán hoạt động.
  3. Đo thời gian chạy với 100, 1.000 và 10.000 phần tử, rồi so sánh với một cách giải khác.
Chạy trong trình biên dịch Python →

Lỗi hay gặp

Dùng < thay vì <= trong vòng lặp

Với low < high, giá trị nằm ở vị trí cuối cùng còn lại sẽ không bao giờ được kiểm tra.

Sai
while low < high:
Cách sửa
while low <= high:

Không bước qua vị trí giữa

Gán low = middle có thể khiến vòng lặp xét mãi cùng một vị trí giữa.

Sai
low = middle
Cách sửa
low = middle + 1

Bạn học xong bài này chưa?

Đánh dấu đã học để theo dõi tiến độ của bạn.

Luyện tập với thử thách

Áp dụng kiến thức của bài học này để giải một bài toán thực tế. Mỗi thử thách chạy ngay trên trình duyệt, có kiểm thử tức thì và AI nhận xét.

Tất cả thử thách