Thuật toán tìm kiếm nhị phân hoạt động trên danh sách đã được sắp xếp. Để tìm “Trang” trong danh sách trên, bạn cần làm như sau:

Danh sách đã sắp xếp

Trước tiên, sắp xếp danh sách theo thứ tự từ điển:

1. anh

2. bích

3. công

4. dương

5. Hà

6. khánh

7. mại

8. trang

Các bước thực hiện thuật toán tìm kiếm nhị phân

1. Xác định giới hạn ban đầu:

• Đặt chỉ số trái (left) = 1 (phần tử đầu tiên).

• Đặt chỉ số phải (right) = 8 (phần tử cuối cùng).

2. Tính chỉ số giữa:

• Chỉ số giữa (mid) = .

• Lấy giá trị tại mid và so sánh với giá trị cần tìm (“trang”).

3. So sánh phần tử giữa:

• Nếu phần tử giữa nhỏ hơn “trang”, di chuyển giới hạn trái lên: left = mid + 1.

• Nếu phần tử giữa lớn hơn “trang”, di chuyển giới hạn phải xuống: right = mid - 1.

• Nếu phần tử giữa bằng “trang”, trả về chỉ số mid.

4. Lặp lại bước 2-3:

• Tiếp tục tính lại chỉ số giữa với giới hạn mới.

• So sánh cho đến khi tìm thấy “trang” hoặc danh sách không còn phần tử nào (khi left > right).

Minh họa thực hiện tìm kiếm

• Lần 1:

• left = 1, right = 8, mid = (1 + 8) // 2 = 4.

• Giá trị tại chỉ số 4 là “dương”. So sánh: “dương” < “trang”.

• Cập nhật left = mid + 1 = 5.

• Lần 2:

• left = 5, right = 8, mid = (5 + 8) // 2 = 6.

• Giá trị tại chỉ số 6 là “khánh”. So sánh: “khánh” < “trang”.

• Cập nhật left = mid + 1 = 7.

• Lần 3:

• left = 7, right = 8, mid = (7 + 8) // 2 = 7.

• Giá trị tại chỉ số 7 là “mại”. So sánh: “mại” < “trang”.

• Cập nhật left = mid + 1 = 8.

• Lần 4:

• left = 8, right = 8, mid = (8 + 8) // 2 = 8.

• Giá trị tại chỉ số 8 là “trang”. So sánh: “trang” == “trang”.

• Tìm thấy “trang” tại chỉ số 8.

Kết quả

“Trang” nằm ở vị trí 8 trong danh sách.