Tìm kiếm một số trong một danh sách được sắp xếp với thuật toán tìm kiếm nhị phân

Giới thiệu

Bạn đã bao giờ đối mặt với việc tìm kiếm một số trong một danh sách lớn và muốn làm điều đó nhanh chóng? Thuật toán tìm kiếm nhị phân sẽ giúp bạn giải quyết vấn đề này một cách hiệu quả.

Yêu cầu bài toán

Chúng ta cần viết một chương trình Python để tìm kiếm một số trong một danh sách được sắp xếp. Sử dụng thuật toán tìm kiếm nhị phân để giảm cần thiết số lần so sánh.

Bạn đang xem: Tìm kiếm một số trong một danh sách được sắp xếp với thuật toán tìm kiếm nhị phân

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

Thuật toán tìm kiếm nhị phân là một thuật toán tìm kiếm trong một danh sách được sắp xếp. Điều này có nghĩa là chúng ta cần sắp xếp danh sách theo thứ tự tăng hoặc giảm dần để áp dụng thuật toán tìm kiếm nhị phân.

Thuật toán này sử dụng kỹ thuật “chia để trị” để tìm kiếm một phần tử trong danh sách. Nguyên tắc hoạt động là so sánh giá trị của phần tử nằm ở giữa danh sách với giá trị cần tìm dẫn đến 1 trong 3 trường hợp:

• Nếu giá trị của phần tử ở giữa bằng giá trị cần tìm, thuật toán trả về chỉ số của phần tử này.
• Nếu giá trị của phần tử ở giữa lớn hơn giá trị cần tìm, thuật toán tìm kiếm trong nửa đầu tiên của danh sách (bên trái phần tử ở giữa).
• Nếu giá trị của phần tử ở giữa nhỏ hơn giá trị cần tìm, thuật toán tìm kiếm trong nửa thứ hai của danh sách (bên phải phần tử ở giữa).

Thuật toán này tiếp tục chia đôi danh sách và tiếp tục tìm kiếm cho đến khi tìm thấy giá trị.

Lưu ý:

• Độ phức tạp của thuật toán tìm kiếm nhị phân là O(log n). Thuật toán tìm kiếm nhị phân nhanh hơn rất nhiều so với tìm kiếm tuần tự vì nó chỉ phải xử lý log n lần thay vì n lần.
• Các trường hợp không nên áp dụng thuật toán tìm kiếm nhị phân:
  • Danh sách chưa được sắp xếp.
  • Danh sách quá nhỏ (giảm hiệu suất).
  • Danh sách có các phần tử trùng lặp.

Giải thích qua ví dụ

Hãy tìm kiếm số 8 trong mảng arr[]={1, 3, 4, 5, 8, 12, 23} bằng thuật toán tìm kiếm nhị phân.

Lần 1: Khởi tạo L = 0 và R = n-1 = 6 (trong đó n=7 là độ dài của mảng), ta có M=(L+R)/2 = (0+6)/2=3.

Lần 2: Lúc này, L = 4, R = 6 nên M=(L+R)/2 = (4+6)/2=5.

Lần 3: Hiện tại, L = 4, R=4 nên M=(L+R)/2 = (4+4)/2=4.

Xem thêm : Các cụm động từ đi với giới từ thông dụng nhất 2023

So sánh ta thấy arr[M] = 8 = target = 8, đã tìm thấy mục tiêu tại vị trí 4.

Định hướng cách làm

Để giải quyết bài toán, bạn có thể thực hiện các bước:

1. Định nghĩa hàm binary_search(arr, x) nhận đầu vào là danh sách arr và giá trị tìm kiếm x.
2. Khởi tạo biến left và right đại diện cho đoạn của danh sách mà chúng ta đang xét. Ban đầu, left được đặt bằng 0 và right được đặt bằng độ dài danh sách trừ 1.
3. Bắt đầu vòng lặp while, trong đó chúng ta sẽ lặp lại cho đến khi left lớn hơn right.
4. Tính chỉ số mid của phần tử ở giữa của đoạn đang xét bằng cách lấy trung bình của left và right và làm tròn xuống về số nguyên bằng toán tử //.
5. So sánh phần tử ở chỉ số mid với giá trị tìm kiếm x. Nếu phần tử bằng x, trả về chỉ số mid.
6. Nếu phần tử ở chỉ số mid nhỏ hơn giá trị tìm kiếm x, điều chỉnh biến left để bằng mid + 1 để tiếp tục tìm kiếm phía bên phải của mid.
7. Nếu phần tử ở chỉ số mid lớn hơn giá trị tìm kiếm x, điều chỉnh biến right để bằng mid - 1 để tiếp tục tìm kiếm phía bên trái của mid.
8. Nếu không tìm thấy giá trị tìm kiếm x trong danh sách, trả về -1.

Kết luận

Dù bài giảng được hướng dẫn với ngôn ngữ Python nhưng bạn hoàn toàn có thể diễn đạt bài toán này bằng các ngôn ngữ C++, C#, Java,… một cách tương tự.

Nếu bạn có cách làm hiệu quả hơn / tối ưu hơn, hoặc cách diễn đạt dễ hiểu hơn, hãy để lại source code hoặc hướng dẫn bên dưới bình luận để mọi người có thể tham khảo và học hỏi thêm.

Thảo luận

Nếu bạn có bất kỳ khó khăn hay thắc mắc gì về khóa học, đừng ngần ngại đặt câu hỏi trong phần BÌNH LUẬN bên dưới hoặc trong mục HỎI & ĐÁP trên thư viện Howkteam.com để nhận được sự hỗ trợ từ cộng đồng

Nguồn: https://ispacedanang.edu.vn
Danh mục: Học tập