Giáo án và PPT Tin học 7 kết nối Bài 15: Thuật toán tìm kiếm nhị phân

BÀI 15: THUẬT TOÁN TÌM KIẾM NHỊ PHÂN 

HOẠT ĐỘNG KHỞI ĐỘNG

GV yêu cầu HS thảo luận và trả lời:

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?

HOẠT ĐỘNG HÌNH THÀNH KIẾN THỨC

Hoạt động 1. TÌM HIỂU THUẬT TOÁN TÌM KIẾM NHỊ PHÂN

GV cho học sinh hoạt động thảo luận nhóm và trả lời câu hỏi: “hãy viết các bước thực hiện thuật toán tìm kiếm nhị phân?”

Sản phẩm dự kiến:

- 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, gọi là tìm kiếm nhị phân.

- 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 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 tìm kiếm không còn phần tử nào (Bước 1)

- Lưu ý: “nửa trước” và “nửa sau” không gồm phần tử giữa

Hoạt động 2. Tìm hiểu sắp xếp và tìm kiếm

- Sắp xếp giúp cho việc tìm kiếm được thực hiện nhanh hơn

HOẠT ĐỘNG LUYỆN TẬP

Từ nội dung bài học, GV yêu cầu HS hoàn thành các bài tập trắc nghiệm sau:

Câu 1: Tư tưởng của thuật toán tìm kiếm nhị phân là gì?

A. Tìm kiếm dựa vào cây tìm kiếm.

B. Tìm kiếm từ đầu đến cuối dãy.

C. Tại mỗi bước tiến hành so sánh X với phần tử giữa của dãy. Dựa vào bước so sánh này quyết định tìm kiếm ở nửa đầu hay ở nửa sau của danh sách.

D. So sánh X lần lượt với các phần tử a₁, a₂, …, a_n

Câu 2: Tại mỗi bước lặp, thuật toán tìm kiếm nhị phân sẽ:

A. Thu hẹp danh sách tìm kiếm chỉ còn một nửa.

B. Danh sách sẽ được sắp xếp lại.

C. Các phần tử trong danh sách sẽ giảm một nửa.

Câu 3: Thuật toán tìm kiếm nhị phân thực hiện trên danh sách nào?

A. Đã được hoán đổi.

B. Đã được sắp xếp.

C. Đã được chỉnh sửa

Câu 4: Thuật toán tìm kiếm nhị phân bắt đầu thực hiện ở vị trí nào trong danh sách?

A. Vị trí đầu tiên.

B. Vị trí cuối cùng.

C. Vị trí giữa.

D. Bất kì vị trí nào.

Câu 5: Điều kiện dừng trong thuật toán tìm kiếm nhị phân là gì?

A. Khi tìm đến giá trị cuối cùng trong danh sách.

B. Khi chưa tìm thấy

C. Khi đã chưa tìm thấy và chưa hết danh sách.

D. Khi đã tìm thấy hoặc khi đã hết danh sách.

Sản phẩm dự kiến:

HOẠT ĐỘNG VẬN DỤNG

Vận dụng kiến thức, GV yêu cầu HS trả lời câu hỏi:

Câu 1: Em tìm một từ tiếng Anh trong quyển từ điển theo cách nào? Tại sao em lại dùng cách đó?