Lý thuyết bài học

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ố.

Ví dụ 1: Tìm x = 44 trong dãy 8 phần tử đã sắp xếp thứ tự không giảm.

- Minh họa các bước:

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

L­ượt thứ nhất: a_giữa là a₄ = 42; 42 < 44 = x
➩ vùng tìm kiếm thu hẹp trong phạm vi từ a₅ → a₈ 

L­ượt thứ hai: a_giữa là a₆ = 55; 55 > 44
➩ vùng tìm kiếm thu hẹp trong phạm vi là a₅ 

L­ượt thứ ba: a_giữa là a₅ = 44; 44 = 44 = x

➩ Vậy số cần tìm là i = 5.

 Ví dụ 2: Tìm x = 21 trong dãy 10 phần tử đã sắp xếp thứ tự không giảm.

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

L­ượt thứ nhất: a_giữa là a₅ = 9; 9 < 21
➩ vùng tìm kiếm thu hẹp trong phạm vi từ a₆ → a₁₀ 

L­ượt thứ hai: a_giữa là a₈ = 30; 30 > 21
➩ vùng tìm kiếm thu hẹp trong phạm vi từ a₆ → a₇ 

L­ượt thứ ba: a_giữa là a₆ = 21; 21= 21
 ➩ Vậy số cần tìm là i = 6.

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

- Thuật toán tìm kiếm nhị phân là thuật toán tìm kiếm x trong dãy đã sắp thứ tự với ý tưởng chia đôi dần để giảm nhanh phạm vi tìm kiếm.

- Mô tả thuật toán:

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

- Để giải một bài toán lớn, người ta tìm cách chia bài toán ban đầu ra thành các bài toán nhỏ hơn rồi giải những bài toán nhỏ hơn sẽ dễ hơn. Cách làm này gọi là “chia để trị”.

- 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 đó. Áp dụng liên tiếp cách này cho đến khi nhận được kết quả.