Nội dung bài viết

    Xem thêm

    Lý thuyết Tin Học 7 Bài 2 (Cánh diều): Tìm kiếm nhị phân

    Tóm tắt lý thuyết Tin Học lớp 7 Bài 2: Tìm kiếm nhị phân ngắn gọn, chi tiết sách Cánh diều sẽ giúp học sinh nắm vững kiến thức trọng tâm, ôn luyện để học tốt Tin Học 7.

    1 1,725 12/01/2023
    Tải về
    Trang trước
    Chia sẻ
    Trang sau  

    Lý thuyết Tin Học 7 Bài 2: Tìm kiếm nhị phân

    1. Chia đôi dần để tìm kiếm một số trong dãy số đã sắp thứ tự

    Ý tưởng chia đôi dần để tìm một số trong một dãy số được minh họa bởi ví dụ sau đây:

    Ví dụ: Tìm x = 44 trong dãy 8 phần tử đã xếp thứ tự không giảm 6, 12, 18, 42, 44, 55, 67, 94. Bảng dưới minh họa từng bước chia đôi dần để tìm kiếm.

    Lý thuyết Tin Học 7 Bài 2: Tìm kiếm nhị phân - Kết nối tri thức (ảnh 1)

    Chia đôi lần 1: Phạm vi tìm kiếm là dãy từ a1 đến a8. Lấy a4 là số có vị trí giữa dãy: Vì x > a4 nên nửa đầu dãy chắc chắn không chứa x = 44, sau đó cần tìm trong nửa sau của dãy. Như vậy, phạm vi tìm kiếm tiếp theo là dãy từ a5 đến a8.

    Chia đôi lần 1: Phạm vi tìm kiếm là dãy từ a5 đến a8. Lấy a6 là số có vị trí giữa dãy; Vì x < a6 nên nửa sau dãy chắc chắn không chứa x = 44, tiếp theo chỉ cần tìm trong nửa đầu của dãy. Như vậy, phạm vi tìm kiếm tiếp theo là dãy con chỉ còn một từ a5.

    Phạm vi tìm kiếm chỉ còn một số. Kết thúc thuật toán với kết quả: Tìm thấy x ở vị trí thứ năm.

    2. Thuật toán tìm kiếm nhị phân

    - Thuật toán tìm kiếm nhị phân chỉ áp dụng được cho dãy đã sắp thứ tự.

    - Ý tưởng: Chia đôi dần để giảm nhanh phạm vi tìm kiếm.

    Lý thuyết Tin Học 7 Bài 2: Tìm kiếm nhị phân - Kết nối tri thức (ảnh 1)

    Hình 2.1: Một mô tả của thuật toán tìm kiếm nhị phân

    Khi bắt đầu thuật toán, phạm vi tìm kiếm là dãy đã cho ban đầu. Lấy phần tử đứng giữa dãy là am để so sánh với x. Nếu am = x thì kết thúc. Trái lại, sẽ có hai trường hợp:

    - Nếu am < x thì chắc chắn không có x trong nửa đầu của dãy.

    - Nếu x < am thì chắc chắn không có x trong nửa sau của dãy.

    Lặp lại theo cách như thế cho đến khi hoặc tìm thấy hoặc độ dài dãy phạm vi tìm kiếm là bằng 0.

    3. Phương pháp “chia để trị” với bài toán tìm kiếm

    - Thuật toán tìm kiếm nhị phân chia bài toán ban đầu thành hai bài toán con nhỏ hơn và chỉ phải tiếp tục giải một trong hai bài toán con đó, cho đến đi nhận được kết quả.

    Xem thêm lời giải bài tập Tin học lớp 7 Cánh diều hay, chi tiết khác:

    Lý thuyết Bài 15: Thực hành tổng hợp bài trình chiếu

    Lý thuyết Bài 1: Tìm kiếm tuần tự

    Lý thuyết Bài 3: Sắp xếp chọn

    Lý thuyết Bài 4: Sắp xếp nổi bọt

    Lý thuyết Bài 5: Thực hành mô phỏng các thuật toán tìm kiếm, sắp xếp

    Tham khảo các loạt bài Tin học 7 khác:

    Bài viết cùng lớp mới nhất

    Xem thêm
    1 1,725 12/01/2023
    Tải về
    Trang trước
    Chia sẻ
    Trang sau  

    Xem thêm các chương trình khác: