🧠 CHIA SẺ VỀ THUẬT TOÁN TÌM KIẾM TRONG LẬP TRÌNH
🎯 1. Mục tiêu bài học
Hiểu khái niệm thuật toán tìm kiếm là gì.
Biết được 2 thuật toán tìm kiếm cơ bản: Tìm kiếm tuyến tính (Linear Search) và Tìm kiếm nhị phân (Binary Search).
Vận dụng lập trình Python để cài đặt các thuật toán này.
Thực hành giải bài toán sử dụng thuật toán tìm kiếm.
📚 2. Lý thuyết cơ bản
🔍 2.1. Tìm kiếm là gì?
Tìm kiếm là quá trình tìm một phần tử có giá trị thỏa mãn điều kiện nào đó trong một tập hợp (danh sách, mảng,...).
🔁 2.2. Thuật toán Tìm kiếm tuyến tính (Linear Search)
Tìm từng phần tử trong danh sách, từ đầu đến cuối.
Phù hợp với danh sách chưa sắp xếp.
✅ Ưu điểm: Đơn giản, dễ cài đặt.
❌ Nhược điểm: Tốc độ chậm khi danh sách lớn (O(n)).
🧩 Ví dụ minh hoạ:
🧮 2.3. Thuật toán Tìm kiếm nhị phân (Binary Search) Áp dụng với danh sách đã sắp xếp. Chia đôi danh sách, so sánh với phần tử ở giữa. ✅ Ưu điểm: Rất nhanh, độ phức tạp O(log n). ❌ Nhược điểm: Phải sắp xếp trước. 🧩 Ví dụ minh hoạ: ▶️ Giải thích chi tiết ví dụ: left là chỉ số đầu danh sách, right là cuối. mid là phần tử giữa, so sánh arr[mid] với x: Nếu bằng → tìm thấy. Nếu nhỏ hơn → bỏ qua nửa trái. Nếu lớn hơn → bỏ qua nửa phải. 🧪 Thử nghiệm: 🎓 3. Bài tập có lời giải chi tiết 🧠 Bài 1: Tìm kiếm số lẻ đầu tiên trong danh sách Yêu cầu: Viết hàm tìm số lẻ đầu tiên trong danh sách. Lời giải: ✅ Giải thích: Duyệt từng phần tử, kiểm tra nếu là số lẻ (% 2 == 1) thì trả về. 🧪 Thử: 🧠 Bài 2: Kiểm tra một số có tồn tại trong danh sách đã sắp xếp chưa? Yêu cầu: Viết hàm kiểm tra số x có trong danh sách sắp xếp chưa? Lời giải: ✅ Giải thích: Dùng lại binary_search, nếu trả về khác -1 nghĩa là có tồn tại. 🧪 Thử: 🧠 Bài 3: Đếm số lần xuất hiện của phần tử x trong danh sách ✅ Giải thích: Duyệt danh sách, nếu phần tử bằng x thì tăng biến đếm. 🧪 Thử: 📌 4. Tổng kết Thuật toán Dùng khi Tốc độ Độ phức tạp Linear Search Danh sách chưa sắp xếp Chậm O(n) Binary Search Danh sách đã sắp xếp Rất nhanh O(log n)
🎯 1. Mục tiêu bài học
Hiểu khái niệm thuật toán tìm kiếm là gì.
Biết được 2 thuật toán tìm kiếm cơ bản: Tìm kiếm tuyến tính (Linear Search) và Tìm kiếm nhị phân (Binary Search).
Vận dụng lập trình Python để cài đặt các thuật toán này.
Thực hành giải bài toán sử dụng thuật toán tìm kiếm.
📚 2. Lý thuyết cơ bản
🔍 2.1. Tìm kiếm là gì?
Tìm kiếm là quá trình tìm một phần tử có giá trị thỏa mãn điều kiện nào đó trong một tập hợp (danh sách, mảng,...).
🔁 2.2. Thuật toán Tìm kiếm tuyến tính (Linear Search)
Tìm từng phần tử trong danh sách, từ đầu đến cuối.
Phù hợp với danh sách chưa sắp xếp.
✅ Ưu điểm: Đơn giản, dễ cài đặt.
❌ Nhược điểm: Tốc độ chậm khi danh sách lớn (O(n)).
🧩 Ví dụ minh hoạ:
🧮 2.3. Thuật toán Tìm kiếm nhị phân (Binary Search) Áp dụng với danh sách đã sắp xếp. Chia đôi danh sách, so sánh với phần tử ở giữa. ✅ Ưu điểm: Rất nhanh, độ phức tạp O(log n). ❌ Nhược điểm: Phải sắp xếp trước. 🧩 Ví dụ minh hoạ: ▶️ Giải thích chi tiết ví dụ: left là chỉ số đầu danh sách, right là cuối. mid là phần tử giữa, so sánh arr[mid] với x: Nếu bằng → tìm thấy. Nếu nhỏ hơn → bỏ qua nửa trái. Nếu lớn hơn → bỏ qua nửa phải. 🧪 Thử nghiệm: 🎓 3. Bài tập có lời giải chi tiết 🧠 Bài 1: Tìm kiếm số lẻ đầu tiên trong danh sách Yêu cầu: Viết hàm tìm số lẻ đầu tiên trong danh sách. Lời giải: ✅ Giải thích: Duyệt từng phần tử, kiểm tra nếu là số lẻ (% 2 == 1) thì trả về. 🧪 Thử: 🧠 Bài 2: Kiểm tra một số có tồn tại trong danh sách đã sắp xếp chưa? Yêu cầu: Viết hàm kiểm tra số x có trong danh sách sắp xếp chưa? Lời giải: ✅ Giải thích: Dùng lại binary_search, nếu trả về khác -1 nghĩa là có tồn tại. 🧪 Thử: 🧠 Bài 3: Đếm số lần xuất hiện của phần tử x trong danh sách ✅ Giải thích: Duyệt danh sách, nếu phần tử bằng x thì tăng biến đếm. 🧪 Thử: 📌 4. Tổng kết Thuật toán Dùng khi Tốc độ Độ phức tạp Linear Search Danh sách chưa sắp xếp Chậm O(n) Binary Search Danh sách đã sắp xếp Rất nhanh O(log n)
▶️ Giải thích chi tiết ví dụ:
arr là danh sách các phần tử.
x là giá trị cần tìm.
Duyệt từng phần tử, nếu phần tử bằng x thì trả về vị trí i.
Nếu duyệt xong mà không thấy thì trả về -1.
🧪 Thử nghiệm:
📌 Danh sách bình luận