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

BÀI 13: THUẬT TOÁN TÌM KIẾM NHI PHÂN - TIN HỌC 7

I. Sau khi kết thúc bài học này học sinh có thể:

• Trình bày khái niệm tìm kiếm nhị phân là tìm kiếm trong danh sách đã sắp xếp.
• Phân biệt được tìm kiếm tuyến tính và tìm kiếm nhị phân.
• Nêu được các bước thực hiện thuật toán tìm kiếm nhị phân.
• Mô tả và giải thích được thuật toán tìm kiếm nhị phân bằng lời hoặc bằng sơ đồ khối.
• So sánh hiệu quả giữa tìm kiếm nhị phân và tuyến tính trong các tình huống khác nhau.

II. Kiến thức cơ bản:

1. Tìm kiếm nhị phân là gì?

• Tìm kiếm nhị phân là thuật toán tìm kiếm một phần tử trong danh sách đã được sắp xếp bằng cách liên tục chia đôi danh sách để thu hẹp phạm vi tìm kiếm.

Hoặc: 

Tìm kiếm nhị phân là một phương pháp tìm kiếm hiệu quả trong danh sách có thứ tự (đã sắp xếp), bằng cách so sánh phần tử cần tìm với phần tử ở giữa danh sách để quyết định tiếp tục tìm ở nửa trái hay nửa phải.

2. Khi nào sử dụng thuật toán tìm kiếm nhị phân

• Tìm vị trí của phần tử cần tìm trong một danh sách đã được sắp xếp theo thứ tự tăng (hoặc giảm).
• Chia đôi danh sách mỗi lần để giảm phạm vi tìm kiếm, cho đến khi:
• Tìm thấy phần tử cần tìm → trả về vị trí được tìm thấy.
• Vượt ra ngoài phạm vi tìm kiếm → thông báo không tìm thấy.
• Khi danh sách đã được sắp xếp.
• Khi cần tìm kiếm nhanh, hiệu quả trong danh sách lớn.

3. Khám phá bằng mô phỏng

3.1 Dữ liệu đầu vào:

• Nhập số phần tử cho mảng -> Tạo mảng mới
• Nhập giá trị phần tử cần tìm

3.2 Thuật toán tìm kiếm nhị phân:

Giả sử ta có một mảng đã sắp xếp tăng dần:  [1, 3, 5, 7, 9, 11, 13]
Và cần tìm x = 9.

Các bước:

3.2.1.  Đặt left = 0, right = độ dài mảng - 1

3.2.2.  Lặp lại khi left <= right:

o    Tính mid = (left + right) // 2

o    Nếu [mid] == x → Tìm thấy, trả về mid

o    Nếu [mid] < x → Tìm bên phải: left = mid + 1

o    Nếu [mid] > x → Tìm bên trái: right = mid - 1

 3.2.3 Nếu ra khỏi vòng lặp mà chưa tìm thấy → Trả về -1 (không tìm thấy)

Hướng dẫn các bước thực hiện mô phỏng thuật toán tìm kiếm nhị phân:

• Bước 1: Học sinh nhập số phần tử 
• Bước 2: Tạo mảng mới -> Xuất hiện dãy số với số phần tử vừa tạo (dãy số tăng dần)
• Bước 3: Nhập phần tử cần tìm 
• Bước 4: Chọn nút bắt đầu tìm kiếm. Ở bước này, học sinh có thể lựa chọn tìm thủ công, từng bước để tiến hành quan sát, hoặc chọn nút tìm kiếm tự động.
• Bước 5: Chọn tốc độ tìm kiếm: (Chậm, trung bình, nhanh).
• Bước 6: Chọn tìm kiếm tự động nếu muốn tìm kiếm nhanh

Mô phỏng thuật toán tìm kiếm nhị phân

Chậm Trung bình Nhanh

Left

Right

Mid

Phần tử tìm thấy

Ngoài phạm vi tìm kiếm

L

M

R

Nhật ký thực thi:

so sánh tìm kiếm Tuần tự và Nhị phân

Nhập danh sách số, cách nhau bởi dấu phẩy: Nhập giá trị cần tìm:

PHIẾU HỌC TẬP CẤU TRÚC TÌM KIẾM NHỊ PHÂN

Câu 1: Em hãy trình bày điều kiện áp dụng và nguyên lý hoạt động của thuật toán tìm kiếm nhị phân.

Câu 2: Cho mảng đã sắp xếp: [2, 5, 8, 12, 16, 23, 38]. Hãy mô tả chi tiết từng bước thuật toán tìm kiếm nhị phân khi tìm giá trị x = 16

Câu 3: Em hãy trình bày các bước tìm kiếm nhị phân trong danh sách a = [3, 5, 7, 9, 11, 45, 89] với phần tử cần tìm là 17.

Câu 4: Giả sử một mảng có 1023 phần tử đã được sắp xếp. Em hãy xác định số lần so sánh tối đa mà thuật toán tìm kiếm nhị phân cần thực hiện để tìm một phần tử. Giải thích vì sao

Câu 5: Trong trường hợp dữ liệu chưa sắp xếp, hãy phân tích lý do không thể sử dụng tìm kiếm nhị phân.

Câu 6 (*): Đánh giá hiệu quả của hai thuật toán khi áp dụng cho các hệ thống tìm kiếm thời gian thực như tìm kiếm người dùng trong mạng xã hội.

Câu 7: Nếu em phải chọn một trong hai thuật toán để tìm kiếm phần tử trong một danh sách lớn nhưng thay đổi thường xuyên, em sẽ chọn thuật toán nào? Giải thích lý do.

✅ Cảm ơn bạn đã gửi thông tin!

Đánh giá bài viết:

★ ★ ★ ★ ★