Các thuật toán tìm kiếm trong Python

Thuật toán tìm kiếm là một phần quan trọng trong lập trình. Nó giúp chúng ta tìm kiếm một giá trị trong một danh sách hoặc mảng. Trong bài viết này, chúng ta sẽ tìm hiểu về hai thuật toán tìm kiếm phổ biến trong Python là tìm kiếm tuần tự (Sequential Search) và tìm kiếm nhị phân (Binary Search).

Thuật toán tìm kiếm tuần tự (Sequential Search)

Thuật toán tìm kiếm tuần tự là một phương pháp đơn giản để tìm kiếm một giá trị trong một danh sách. Thuật toán này kiểm tra từng phần tử trong danh sách cho đến khi tìm thấy giá trị cần tìm hoặc kiểm tra hết toàn bộ danh sách mà không tìm thấy.

Bạn đang xem: Các thuật toán tìm kiếm trong Python

Quá trình của thuật toán tìm kiếm tuần tự bao gồm các bước sau:

1. Duyệt qua từng phần tử của danh sách theo thứ tự, bắt đầu từ phần tử đầu tiên.
2. So sánh phần tử hiện tại với giá trị cần tìm kiếm.
3. Nếu tìm thấy giá trị, trả về chỉ số của phần tử đó.
4. Nếu đã duyệt qua toàn bộ danh sách mà không tìm thấy giá trị, trả về -1.

Thuật toán tìm kiếm tuần tự giúp tìm kiếm hiệu quả trong các danh sách nhỏ hoặc khi muốn tìm kiếm một phần tử cụ thể trong danh sách không được sắp xếp. Tuy nhiên, nếu danh sách lớn, thuật toán này có độ phức tạp thời gian là O(n), nên không luôn là lựa chọn tốt nhất.

Hình ảnh minh họa thuật toán tìm kiếm tuần tự

Thuật toán tìm kiếm nhị phân (Binary Search)

Xem thêm : Hướng dẫn xem ngày tốt sửa bếp theo tuổi

Thuật toán tìm kiếm nhị phân là một phương pháp tìm kiếm hiệu quả được sử dụng trong các danh sách đã được sắp xếp. Thuật toán này hoạt động bằng cách chia đôi danh sách và so sánh giá trị tại điểm chia với giá trị cần tìm kiếm. Nếu giá trị tại điểm chia bằng giá trị cần tìm kiếm, thuật toán kết thúc. Nếu không, nó sẽ tiếp tục tìm kiếm trong một nửa của danh sách dựa trên kết quả so sánh và loại bỏ nửa còn lại.

Quá trình của thuật toán tìm kiếm nhị phân bao gồm các bước sau:

1. Xác định chỉ số bắt đầu (left) và chỉ số kết thúc (right) của danh sách.
2. Tính điểm chính giữa của danh sách (mid) bằng cách lấy trung bình của left và right.
3. So sánh giá trị tại điểm chính giữa (arr[mid]) với giá trị cần tìm kiếm.
4. Nếu tìm thấy giá trị, trả về chỉ số của phần tử.
5. Nếu giá trị tại điểm chính giữa lớn hơn giá trị cần tìm kiếm, thuật toán tiếp tục tìm kiếm trong nửa trái của danh sách (cập nhật right).
6. Nếu giá trị tại điểm chính giữa nhỏ hơn giá trị cần tìm kiếm, thuật toán tiếp tục tìm kiếm trong nửa phải của danh sách (cập nhật left).
7. Lặp lại quá trình cho đến khi tìm thấy giá trị hoặc left > right. Nếu không tìm thấy, trả về -1.

Thuật toán tìm kiếm nhị phân có độ phức tạp thời gian là O(log n), nơi n là số phần tử trong danh sách. Điều này làm cho nó rất hiệu quả và phù hợp cho các danh sách lớn. Tuy nhiên, trước khi áp dụng thuật toán tìm kiếm nhị phân, danh sách phải được sắp xếp.

Hình ảnh minh họa thuật toán tìm kiếm nhị phân

Sử dụng các hàm tìm kiếm có sẵn trong Python

Ngoài hai thuật toán tìm kiếm trên, Python cung cấp một số hàm và phương thức tìm kiếm có sẵn để giúp bạn tìm kiếm giá trị trong danh sách hoặc dãy dữ liệu. Dưới đây là một số trong những hàm và phương thức này:

Phương thức list.index()

Phương thức index() được sử dụng để tìm chỉ số của một giá trị cụ thể trong danh sách. Nếu giá trị không tồn tại trong danh sách, phương thức này sẽ ném ra một ngoại lệ ValueError.

Toán tử in operator

Xem thêm : 101+ cách đặt tên tiếng Anh hay cho nữ sang chảnh, cao quý và ý nghĩa

Toán tử in được sử dụng để kiểm tra xem một giá trị có tồn tại trong danh sách hay không. Nó trả về một giá trị boolean (True nếu tồn tại và False nếu không tồn tại).

Phương thức count()

Phương thức count() được sử dụng để đếm số lần một giá trị xuất hiện trong danh sách.

Hàm any() và all()

Hàm any() được sử dụng để kiểm tra xem ít nhất một phần tử trong danh sách thỏa mãn một điều kiện cụ thể.

Hàm all() được sử dụng để kiểm tra xem tất cả các phần tử trong danh sách đều thỏa mãn một điều kiện cụ thể.

Lưu ý: Một số phương thức và hàm trên có thể chỉ hoạt động với danh sách đã sắp xếp hoặc không sắp xếp tùy thuộc vào yêu cầu cụ thể của bạn.

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