Bài giảng Môn Tin học lớp 10 - Bài toán và thuật toán nhị phân

TÌM KIẾM NHỊ PHÂN TỔ 4 TÌM KIẾM NHỊ PHÂN @ Xác định bài toán INPUT : Dãy A là dãy tăng gồm N số nguyên khác nhau a1, a2,…,aN và số nguyên k; * OUTPUT : Chỉ số i mà ai = k hoặc thông báo không có số hạng nào của dãy A có giá trị bằng k. TÌM KIẾM NHỊ PHÂN @ Ý tưởng Sử dụng tính chất dãy A đã sắp xếp tăng, ta tìm cách thu hẹp nhanh phạm vi tìm kiếm bằng cách so sánh k với số hạng ở giữa dãy ( agiua), khi đó chỉ xảy ra một trong ba trường hợp : Quá trình trên được lặp đi lặp lại cho đến khi tìm được Output . * Nếu Giữa = k thì xuất Giữa * Nếu Giữa > k thì k nằm trong khoảng Đầu  Giữa * Nếu Giữa k thì đặt Cuối  Giữa – 1, rồi chuyển đến B7; Nếu agiữa Cuối thì thông báo dãy A không có số hạng  có giá trị bằng k, rồi kết thúc; B8: Quay lại B3; B4: B5: B6: * Nếu Giữa = k thì xuất Giữa * Nếu Giữa > k thì k nằm trong khoảng Đầu  Giữa * Nếu Giữa 21 vùng tìm kiếm thu hẹp trong phạm vi từ a6 a7; Lượt thứ ba: agiua là a6 = 21; 21= 21 	 Vậy số cần tìm là i = 6. 22 21 6 6 21 @ MÔ PHỎNG THUẬT TOÁN TÌM KIẾM NHỊ PHÂN Ví dụ 2: