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ínhtìm kiếm nhị phân.





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





Tim kiếm tuyến tính (Linear search)
Tim kiếm tuyến tính (Linear search). Ảnh: GeeksforGeeks




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.





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




Pseudocode





Tìm kiếm tuyến tính - Pseudocode
Tìm kiếm tuyến tính – Pseudocode




Java code





Tìm kiếm tuyến tính - Java code
Tìm kiếm tuyến tính – Java code




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





Tìm kiếm nhị phân - Binary search.Tìm kiếm nhị phân - Binary search.Tìm kiếm nhị phân - Binary search.
Tìm kiếm nhị phân – Binary search. Ảnh: GeeksforGeeks




Đâ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.





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




Pseudocode





Tìm kiếm nhị phân - Pseudocode
Tìm kiếm nhị phân – Pseudocode




Java code





Tìm kiếm nhị phân - Jave code
Tìm kiếm nhị phân – Jave 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


Mobile version will be updated soon

Meanwhile, please use our web version
Thank you and see you there!