Bài giảng Tin học 7 (Kết nối tri thức) - Bài 15: Thuật toán tìm kiếm nhị phân

 BÀI 
15
 Việc kinh doanh mở rộng, số lượng khách hàng của cửa hàng 
 bán giống cây trồng nhà An lên đến hàng trăm người. Việc tìm 
 kiếm tên khách hàng trong danh sách thật khó khăn. Em có gợi 
 ý gì cho bạn An để việc tìm kiếm được dễ dàng hơn không? 1. THUẬT TOÁN TÌM KIẾM NHỊ PHâN
 Khi danh sách khách hàng ngày càng nhiều, để thuận lợi cho việc tìm kiếm, An đã giúp mẹ soạn thảo 
 danh sách khách hàng trên máy tính với tên khách hàng được sắp xếp theo thứ tự chữ cái. Giả sử An 
 cần tìm địa chỉ của khách hàng tên là “Trúc” trong danh sách khách hàng như Hình 15.1.1 Khi danh sách đã được sắp xếp, 
 An không cần tìm từ đầu mà so 
 sánh ngay giá trị cần tìm với giá 
 trị của vị trí ở giữa danh sách.
- Nếu giá trị cần tìm bằng giá trị ở giữa thì tìm thấy và dừng lại
- Nếu lớn hơn thì chỉ cần tìm ở nửa sau của danh sách
- Nếu nhỏ hơn thì tìm ở nửa đầu của danh sách. 
 Lặp lại quá trình đó cho đến khi tìm thấy hoặc hết danh sách. 
 Như vậy, tại mỗi bước lặp, thuật toán tìm kiếm thu hẹp danh sách tìm kiếm chỉ còn một nửa. Do đó thuật toán 
này có tên là tìm kiếm nhị phân (chia đôi). Các bước để An tìm khách hàng tên “Trúc” trong danh sách ở Hình 15.1 theo thuật toán 
 tìm kiếm nhị phân như sau: 
Bước 1. Xét vị trí ở giữa của dãy, đó là vị trí số 5 Bước 2. Xét vị trí ở giữa của nửa sau của dãy là vị trí số 7 Bước 3. Xét vị trí ở giữa của nửa sau còn lại của dãy, đó là vị trí số 8
Vì sau bước 3 đã tìm thấy tên khách hàng nên thuật toán kết thúc. Mô tả thuật toán tìm kiếm nhị phân bằng ngôn ngữ tự nhiên:
Bước 1. Nếu vùng tìm kiếm không có phần tử nào thì kết luận không tìm thấy và thuật toán kết thúc.
Bước 2. Xác định vị trí giữa của vùng tìm kiếm. 
Vị trí này chia vùng tìm kiếm thành hai nửa: nửa trước và nửa sau vị trí giữa.
Bước 3. Nếu giá trị cần tìm bằng giá trị của vị trí giữa thì kết luận “giá trị cần tìm xuất hiện tại vị 
trí giữa” và kết thúc.
Bước 4. Nếu giá trị cần tìm nhỏ hơn giá trị của vị trí giữa thì vùng tìm kiếm mới được thu hẹp 
lại, chỉ còn nửa trước của dãy. Ngược lại (nếu giá trị cần tìm lớn hơn giá trị của vị trí giữa) vùng 
tìm kiếm mới được thu hẹp lại, chỉ còn nửa sau của dãy. 
Bước 5. Lặp lại từ Bước 1 đến Bước 4 cho 
đến khi tìm thấy giá trị cần tìm (Bước 3) hoặc 
vùng tìm kiếm không còn phần tử nào (Bước 1). 2. SẮP XẾP VÀ TÌM KIếM
 Trong ví dụ ở mục 1, khách hàng tên “Trúc” được tìm thấy sau 3 bước thực hiện theo thuật toán tìm kiếm nhị phân, 
 trong khi thuật toán tìm kiếm tuần tự phải thực hiện 8 bước.
Xét trường hợp có một khách hàng nào đó mà mẹ bạn An quên chưa ghi vào sổ, do đó tên khách hàng không có trong danh sách ở 
Hình 15.1. Khi phải tìm kiếm tên khách hàng này, thuật toán tìm kiếm tuần tự cần thực hiện 9 bước để xét hết danh sách và kết 
luận “Không tìm thấy”, trong khi thuật toán tìm kiếm nhị phân chỉ mất 4. bước thực hiện. 
Như vậy, trong ví dụ trên, thuật toán tìm kiếm nhị phân thực hiện tìm kiếm nhanh hơn thuật toán tìm kiếm tuần tự. Có được ưu 
điểm này là do trước khi thực hiện tìm kiếm nhị phân, danh sách khách hàng cần tìm đã được sắp xếp. Nhờ việc danh sách đã 
được sắp xếp, tại mỗi bước, thuật toán tìm kiếm nhị phân thu hẹp được phạm vi tìm kiếm chỉ còn một nửa. L L
 LOVE
 G PIRCE
TẠML BIỆT VÀ SHẸN GẶP LẠI
 T
 H
 L