Vì sao cần có thuật toán tìm kiếm?

Trong thực tế, có rất nhiều bài toán, nhưng hầu như tất cả chúng đều quy về một bài toán duy nhất, đó chính là bài toán tìm kiếm. Ví dụ như khi bạn giải một bài toán, bạn có làm cách nào đi nữa thì mục đích cuối cùng của bạn chính là đi tìm lời giải của bài toán. Hay khi bạn thực hiện sắp xếp, lọc các phần tử của danh sách, mục đích của bạn cũng là tìm kiếm những phần tử thỏa mãn yêu cầu.

Bạn đang xem: Thuật toán tìm kiếm nhanh nhất

Từ những nhu cầu thực tế đó, bài toán tìm kiếm dẫn đến chúng ta phải tạo ra thuật toán tìm kiếm để giải quyết nó. Vậy thì thuật toán tìm kiếm là gì? Thuật toán tìm kiếm (searching algorithm) là thuật toán giúp ta tìm ra trong một tập dữ liệu đã cho một hoặc nhiều phần tử thỏa mãn yêu cầu tìm kiếm.

Tùy theo cấu trúc dữ liệu mà chúng ta sẽ có những thuật toán tìm kiếm khác nhau phù hợp cho mỗi cấu trúc đó. Do đó, chúng ta không nên học thuộc lòng thuật toán tìm kiếm trên một tập dữ liệu, một cấu trúc dữ liệu trong một ngôn ngữ cụ thể nào đó. Hãy học ý tưởng của thuật toán và áp dụng nó linh hoạt cho các cấu trúc dữ liệu khác nhau trong các ngôn ngữ lập trình khác nhau.

Trong bài này, mình sẽ dùng C++ để minh họa cho các thuật toán tìm kiếm, các bạn có thể áp dụng nó cho bất kỳ ngôn ngữ lập trình nào mà các bạn thích như Java hay Python…

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

Trong bài viết này, mình sẽ giới thiệu đến các bạn 3 thuật toán tìm kiếm phổ biến nhất: tìm kiếm tuyến tính, tìm kiếm nhị phân và tìm kiếm nội suy. Giờ hãy bắt đầu tìm hiểu về các thuật toán tìm kiếm này nhé!

Tìm kiếm tuyến tính

Tìm kiếm tuyến tính (linear search) hay tìm kiếm tuần tự (sequential search) là thuật toán tìm kiếm bằng cách duyệt qua tất cả các phần tử của danh sách cho đến khi gặp phần tử cần tìm hoặc là đã hết danh sách. Do cách tìm kiếm duyệt từ đầu đến cuối này, độ phức tạp thời gian của thuật toán này sẽ là O(n).

Chúng ta có một mảng A có n phần tử bắt đầu từ vị trí 0. Để tìm kiếm phần tử x trong mảng A này, ta làm như sau:

Gán i = 0.So sánh giá trị của A và x:Nếu A == x thì dừng và trả về giá trị của i (vị trí của x trong mảng A).Nếu A != x thì sang bước 3.Gán i = i + 1:Nếu i == n (tức hết mảng) thì dừng lại và trả kết quả là -1 (không tìm thấy x).Nếu i
*
Tìm kiếm nhị phân

Thuật toán đã có, giờ hãy xem cài đặt nó trong C++ như thế nào nha:

int BinarySearch(int A<>, int n, int x){ int left = 0; int right = n - 1; int mid; while (left x) right = mid - 1; // Giới hạn khoảng tìm kiếm lại là nửa khoảng trước else if (A Đối với mảng được sắp xếp giảm, các bạn chỉ cần thay đổi chỗ so sánh A và x như sau:

A right = mid – 1A > x:left = mid + 1

Video minh họa ý tưởng thuật toán:


Thuật toán tìm kiếm nhị phân | Khiêm Lê

Tìm kiếm nội suy

Tìm kiếm nội suy (interpolation search) là một thuật toán cải tiến từ thuật toán tìm kiếm nhị phân. Thay vì xác định điểm chính giữa của danh sách, thuật toán tìm kiếm nội suy xác định điểm gần với vị trí của phần tử cần tìm, do đó tối ưu được thời gian hơn so với thuật toán tìm kiếm nhị phân. Độ phức tạp thời gian cũng vì thế mà tốt hơn là O(log(log(n))).

Xem thêm: Cách Cài Font Chữ Cho Zalo Trên Điện Thoại, Hướng Dẫn Cách Đổi Kiểu Chữ Nhắn Tin Trên Zalo

Tuy nhiên, thuật toán tìm kiếm nhị phân luôn ổn định với độ phức tạp thời gian là O(log(n)), thuật toán tìm kiếm nội suy lại không như vậy. Trong những trường hợp xấu nhất như dãy tăng/giảm phân bố không đều, thuật toán tìm kiếm này đạt độ phức tạp là O(n), không khác gì dùng thuật toán tìm kiếm tuyến tính cả. Do đó, bạn nên sử dụng thuật toán tìm kiếm nhị phân để đảm bảo được độ phức tạp O(log(n)).

Vẫn là mảng A, vẫn n phần tử bắt đầu từ 0 và tăng dần. Tìm x trong mảng này dùng thuật toán tìm kiếm nội suy như sau:

Gán left = 0, right = n – 1.Gán mid = left+(right–left)*(x–a)/(a–a):Nếu như A == x:Dừng lại và trả về giá trị của mid.Nếu như A > x:right = mid – 1Nếu như A left = mid + 1Nếu left = A và x Đúng thì quay lại bước 2.Sai thì dừng và trả về kết quả -1 (không tìm thấy x)

Và tương tự với mảng giảm dần, bạn chỉ cần sửa lại:

A right = mid – 1A > x:left = mid + 1

Giờ hãy cùng xem cài đặt thuật toán tìm kiếm nội suy trong C++ với mảng tăng nha:

int InterpolationSearch(int A<>, int n, int x){ int left = 0; int right = n - 1; int mid; while (left = A && x x) right = mid - 1; else if (A Lưu ý: khi sử dụng thuật toán tìm kiếm nhị phân hoặc nội suy, nếu như mảng chưa được sắp xếp, nên sử dụng kèm với các thuật toán sắp xếp có hiệu suất cao như Quick Sort hay Merge Sort để sắp xếp nhằm tối ưu hóa thuật toán. Nếu tìm kiếm nhanh mà sắp xếp chậm cũng không có ý nghĩa gì đối với tập dữ liệu lớn.

Tổng kết

Vậy là qua bài viết này, mình đã giới thiệu đến các bạn 3 thuật toán tìm kiếm phổ biến nhất mà các lập trình viên nên biết. Trong hầu hết các bài tập, các bạn sẽ cần dùng đến các thuật toán tìm kiếm này, đừng quên luyện tập thật nhiều để thành thục các thao tác trên các cấu trúc dữ liệu khác nhau nha.

Nếu như các bạn thấy hay, đừng quên chia sẻ cho bạn bè cùng biết nha. Bạn cũng có thể để lại bình luận bên dưới bài viết nếu có bất kỳ thắc mắc hoặc góp ý nào. Cảm ơn các bạn đã theo dõi bài viết!