Bài giảng Tin học 7 (Kết nối tri thức với cuộc sống) - Bài 15: Thuật toán tìm kiếm nhị phân - Nguyễn Thị Phương Nam

 BÀI 15:
THUẬT TOÁN TÌM KIẾM 
 NHỊ PHÂN MỤC Ø Tìm hiểu về thuật toán tìm kiếm nhị phân
TIÊU Ø Mối liên quan giữa sắp xếp và tìm kiếm 1. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN
 2. SẮP XẾP VÀ TÌM KIẾM 1. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN
Thuật toán tìm kiếm nhị phân là gì?
 Bài toán tìm kiếm khách DANH SÁCH KHÁCH HÀNG
 hàng: Tìm địa chỉ của khách 
 hàng có tên “Trúc” trong TT Họ đệm Tên Địa chỉ
 danh sách sau đây. 1 Nguyễn Hòa 68 Ngô Quyền
 2 Kiều Thị Liên 75 Lê Văn Tám
 3 Ngô Hà Trang Phương Độ, Phúc Thọ
 4 Nguyễn An Xóm 1, Nghĩa Lộ, Võng Xuyên
 5 Thanh Trúc Xóm 2, Lục Xuân, Hòa Hưng
 6 Trần Bình Xóm 3, Thư Trai
 7 Trần Thanh Tước 48 Hoàng Hoa Thám
 8 Ngô Hoàng Phương Xóm 6, Lục Xuân, Hòa Hưng
 9 Hoàng Mai Số 3, Tổ 7, Phúc Hòa 1. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN
Thuật toán tìm kiếm nhị phân là gì?
 Các bước tìm kiếm DANH SÁCH KHÁCH HÀNG
 TT Họ đệm Tên Địa chỉ
 1 Nguyễn HòaAn 68 Ngô QuyềnXóm 1, Nghĩa Lộ, Võng Xuyên
 Sắp xếp danh sách theo tên
 2 TrầnKiều Thị LiênBình 75 Lê Văn TámXóm 3, Thư Trai
 3 Ngô HàNguyễn TrangHòa Phương Độ, Phúc Thọ68 Ngô Quyền
 4 NguyễnKiều Thị AnLiên Xóm 1, Nghĩa Lộ, Võng Xuyên75 Lê Văn Tám
 5 ThanhHoàng TrúcMai Xóm 2, Lục Xuân, Hòa HưngSố 3, Tổ 7, Phúc Hòa
 6 TrầnNgô Hoàng BìnhPhương Xóm 6, Lục Xuân, Hòa HưngXóm 3, Thư Trai
 7 Trần ThanhNgô Hà TướcTrang 48 Hoàng Hoa ThámPhương Độ, Phúc Thọ
 8 ThanhNgô Hoàng TrúcPhương Xóm 2, Lục Xuân, Hòa HưngXóm 6, Lục Xuân, Hòa Hưng
 9 HoàngTrần Thanh TướcMai Số 3, Tổ 7, Phúc Hòa48 Hoàng Hoa Thám 1. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN
 Mai # Trúc
Thuật toán tìm kiếm nhị phân là gì?
 Mai < Trúc
 Các bước tìm kiếm DANH SÁCH KHÁCH HÀNG
 TT Họ đệm Tên Địa chỉ
 1 Nguyễn An Xóm 1, Nghĩa Lộ, Võng Xuyên
 Sắp xếp danh sách theo tên
 2 Trần Bình Xóm 3, Thư Trai
 3 Nguyễn Hòa 68 Ngô Quyền
 Bước 1. Xét vị trí ở giữa 
 4
 của danh sách Kiều Thị Liên 75 Lê Văn Tám
 5 Hoàng Mai Số 3, Tổ 7, Phúc Hòa
 6 Ngô Hoàng Phương Xóm 6, Lục Xuân, Hòa Hưng
 7 Ngô Hà Trang Phương Độ, Phúc Thọ
 8 Thanh Trúc Xóm 2, Lục Xuân, Hòa Hưng
 9 Trần Thanh Tước 48 Hoàng Hoa Thám 1. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN
 Trang # Trúc
Thuật toán tìm kiếm nhị phân là gì?
 Trang < Trúc
 Các bước tìm kiếm DANH SÁCH KHÁCH HÀNG
 TT Họ đệm Tên Địa chỉ
 1 Nguyễn An Xóm 1, Nghĩa Lộ, Võng Xuyên
 Sắp xếp danh sách theo tên
 2 Trần Bình Xóm 3, Thư Trai
 3 Nguyễn Hòa 68 Ngô Quyền
 Bước 1. Xét vị trí ở giữa 
 4
 của danh sách Kiều Thị Liên 75 Lê Văn Tám
 5 Hoàng Mai Số 3, Tổ 7, Phúc Hòa
 Bước 2. Xét vị trí ở giữa 6 Ngô Hoàng Phương Xóm 6, Lục Xuân, Hòa Hưng
 của nửa sau của danh sách 7 Ngô Hà Trang Phương Độ, Phúc Thọ
 8 Thanh Trúc Xóm 2, Lục Xuân, Hòa Hưng
 9 Trần Thanh Tước 48 Hoàng Hoa Thám 1. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN
Thuật toán tìm kiếm nhị phân là gì? Trúc = Trúc
 Các bước tìm kiếm DANH SÁCH KHÁCH HÀNG
 TT Họ đệm Tên Địa chỉ
 1 Nguyễn An Xóm 1, Nghĩa Lộ, Võng Xuyên
 Sắp xếp danh sách theo tên
 2 Trần Bình Xóm 3, Thư Trai
 3 Nguyễn Hòa 68 Ngô Quyền
 Bước 1. Xét vị trí ở giữa 
 4
 của danh sách Kiều Thị Liên 75 Lê Văn Tám
 5 Hoàng Mai Số 3, Tổ 7, Phúc Hòa
 Bước 2. Xét vị trí ở giữa 6 Ngô Hoàng Phương Xóm 6, Lục Xuân, Hòa Hưng
 của nửa sau của danh sách 7 Ngô Hà Trang Phương Độ, Phúc Thọ
 8 Thanh Trúc Xóm 2, Lục Xuân, Hòa Hưng
 Bước 3. Xét vị trí ở giữa 
 9 Trần Thanh Tước 48 Hoàng Hoa Thám
 của nửa sau còn lại của ds 1. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN
Thuật toán tìm kiếm nhị phân là gì? Trúc = Trúc
 Các bước tìm kiếm DANH SÁCH KHÁCH HÀNG
 TT Họ đệm Tên Địa chỉ
 1 Nguyễn An Xóm 1, Nghĩa Lộ, Võng Xuyên
 Sắp xếp danh sách theo tên
 2 Trần Bình Xóm 3, Thư Trai
 3 Nguyễn Hòa 68 Ngô Quyền
 Bước 1. Xét vị trí ở giữa 
 4
 của danh sách Kiều Thị Liên 75 Lê Văn Tám
 5 Hoàng Mai Số 3, Tổ 7, Phúc Hòa
 Bước 2. Xét vị trí ở giữa 6 Ngô Hoàng Phương Xóm 6, Lục Xuân, Hòa Hưng
 của nửa sau của danh sách 7 Ngô Hà Trang Phương Độ, Phúc Thọ
 8 Thanh Trúc Xóm 2, Lục Xuân, Hòa Hưng
 Bước 3. Xét vị trí ở giữa 
 9 Trần Thanh Tước 48 Hoàng Hoa Thám
 của nửa sau còn lại của ds
 Thuật toán tìm kiếm nhị phân 1. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN
Mô tả thuật toán tìm kiếm nhị phân
 Mô tả thuật toá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à kết thúc Nửa trước Nửa sau
 thuật toán
 Vị trí giữa
 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
 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 Nửa trước Nửa sau
 tại vị trí giữa” và kết thúc thuật toán
 Bước 4. Nếu giá trị cần tìm nhỏ hơn giá trị của Vị trí giữa = Phần nguyên [Vị trí đầu + vị trí cuối)/2]
 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, vùng 
 tìm kiếm mớ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)