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

Mục đích chính của thuật toán tìm kiếm là để kiểm tra một phần tử hoặc truy xuất nó từ bất kỳ cấu trúc dữ liệu nào. Các thuật toán tìm kiếm này được phân loại thành hai phần, thường là dựa trên kiểu tìm kiếm.

1. Tìm kiếm tuần tự (Sequential search)

Danh sách hoặc mảng được duyệt qua (traverse) tuần tự và mọi phần tử đều được kiểm tra. Ví dụ: Tìm kiếm tuyến tính

2. Tìm kiếm theo khoảng thời gian (Interval search)

Được thiết kế cho các cấu trúc dữ liệu được sắp xếp và hiệu quả hơn giải thuật tìm kiếm tuần tự vì giải thuật này liên tục nhắm đến trung tâm của cấu trúc dữ liệu và chia đôi không gian tìm kiếm. Ví dụ: Tìm kiếm nhị phân

Trong bài viết này, chúng ta sẽ thảo luận về hai thuật toán tìm kiếm: tìm kiếm tuyến tính và tìm kiếm nhị phân.

Tìm kiếm tuyến tính (Linear Search)

Giải thuật này rất đơn giản, độ phức tạp là O(N). Một tìm kiếm tuần tự được thực hiện cho từng phần tử trong cấu trúc dữ liệu.

Nếu kết quả phù hợp được tìm thấy, nó sẽ được trả về; nếu không, quá trình tìm kiếm sẽ tiếp tục cho đến hết cấu trúc dữ liệu.

Cách tìm kiếm tuyến tính hoạt động

Giả sử ta muốn tìm giá trị x trong mảng A.

Pseudocode

Java code

Tìm kiếm nhị phân (Binary Search)

Đây là một giải thuật tìm kiếm nhanh độ phức tạp là O(logN).

Giải thuật O(logN) được xem là có tính hiệu quả cao vì tỷ lệ giữa số lượng hoạt động so với kích thước của input giảm và có xu hướng bằng không khi N tăng lên. (N là kích thước input tính bằng đơn vị bit cần để đại diện cho input đó).

Việc thu thập dữ liệu phải ở dạng được sắp xếp để giải thuật này hoạt động chính xác.

Cách tìm kiếm nhị phân hoạt động

Tìm kiếm nhị phân tìm kiếm một phần tử cụ thể bằng cách so sánh với phần tử nằm ở ngay chính giữa của mảng.

Nếu kết quả tìm kiếm khớp, thì index của phần tử này sẽ được trả về. Nếu kết quả không khớp, nó sẽ kiểm tra xem phần tử ở giữa có lớn hơn item này hay không, sau đó nó sẽ tìm kiếm phần tử này trong mảng con bên trái của phần tử ở giữa.

Trường hợp phần tử ở giữa nhỏ hơn, nó sẽ tìm kiếm phần tử trong mảng con ở bên phải của phần tử ở giữa. Cho đến khi kích thước mảng con giảm xuống còn 0, quá trình này sẽ tiếp tục tại mảng con.

Để tìm kiếm nhị phân hoạt động, mảng phải được sắp xếp trước.

Giải thuật

Giả sử ta muốn tìm giá trị x trong mảng A đã sắp xếp.

Pseudocode

Java code

Đây là hai giải thuật tìm kiếm được sử dụng phổ biến nhất. Hãy cùng theo dõi các bài viết tiếp theo và thảo luận cùng Gambaru các giải thuật hữu ích khác.

Theo Pulsara Sandeepa