Một số thuật toán tìm kiếm (Search) cơ bản trong cấu trúc dữ liệu

Đây là nhóm thuật toán nền tảng, xuất hiện gần như ở mọi nơi: từ việc tìm kiếm trong mảng, tra cứu user trong database, xử lý index, đến những hệ thống gợi ý, search engine phức tạp.

Bài viết này đóng vai trò như một hub, giới thiệu các thuật toán tìm kiếm cơ bản, cách chúng hoạt động ở mức khái niệm, ưu – nhược điểm và khi nào nên dùng thuật toán nào.

Bài toán tìm kiếm là gì?

Phiên bản đơn giản nhất của bài toán tìm kiếm có thể phát biểu như sau:

• Cho một tập dữ liệu (ví dụ: mảng, danh sách, cây, bảng băm…).
• Cho một khóa (key) hoặc điều kiện (predicate).
• Cần xác định:
  • Phần tử có tồn tại trong tập dữ liệu hay không.
  • Nếu có, trả về vị trí hoặc giá trị tương ứng.

Tùy cách tổ chức dữ liệu (chưa sắp xếp, đã sắp xếp, có index, dùng hash, dùng cây cân bằng, v.v.) mà ta áp dụng thuật toán tìm kiếm tương ứng.

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

Linear Search là thuật toán tìm kiếm đơn giản nhất: duyệt lần lượt từng phần tử trong cấu trúc dữ liệu (thường là mảng hoặc danh sách) và kiểm tra điều kiện.

Ý tưởng:

• Bắt đầu từ phần tử đầu tiên, so sánh với key cần tìm.
• Nếu khớp → trả về vị trí/giá trị.
• Nếu không, tiếp tục đến phần tử tiếp theo.
• Nếu duyệt hết mà vẫn không thấy → kết luận không tồn tại.

Khi nào dùng Linear Search:

• Dữ liệu nhỏ, đơn giản, không đáng để tối ưu phức tạp.
• Cấu trúc dữ liệu không được sắp xếp.
• Cần kiểm tra điều kiện phức tạp, không chỉ là so sánh bằng.

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

Binary Search là thuật toán tìm kiếm hiệu quả trên dữ liệu đã được sắp xếp (thường là mảng tăng dần).

Ý tưởng:

• Xác định chỉ số giữa (mid) của đoạn đang xét.
• So sánh key với phần tử ở mid:
  • Nếu bằng → trả về kết quả.
  • Nếu key nhỏ hơn → tiếp tục tìm trong nửa trái.
  • Nếu key lớn hơn → tiếp tục tìm trong nửa phải.
• Lặp lại cho đến khi tìm thấy hoặc đoạn tìm kiếm rỗng.

Ưu điểm:

• Độ phức tạp O(log n), rất nhanh so với Linear Search.
• Rất phù hợp với dữ liệu lớn nhưng đọc nhiều, ghi ít.

Nhược điểm:

• Bắt buộc dữ liệu phải được sắp xếp theo một thứ tự nào đó.
• Việc chèn/xóa có thể tốn kém nếu cần duy trì thứ tự.

Tìm kiếm bằng Hash (Hash-based Lookup)

Các cấu trúc như Hash Table / Hash Map / Dictionary sử dụng hàm băm (hash function) để ánh xạ key sang một vị trí (bucket) trong bảng.

Ý tưởng:

• Dùng hash function để tính chỉ mục từ key.
• Lưu (hoặc tìm) key tại bucket tương ứng.
• Xử lý va chạm (collision) bằng chain hoặc open addressing.

Ưu điểm:

• Trung bình O(1) cho thao tác tìm kiếm, chèn, xóa.
• Rất mạnh cho các bài toán tra cứu (lookup) nhiều.

Nhược điểm:

• Không đảm bảo thứ tự các phần tử.
• Phụ thuộc vào chất lượng của hash function, load factor, cách xử lý collision.

Khi dùng:

• Tìm kiếm theo key thường xuyên (userId, username, token…).
• Cần hiệu năng O(1) trung bình cho lookup.

Tìm kiếm trong cây tìm kiếm nhị phân (Binary Search Tree – BST)

Binary Search Tree (BST) là cấu trúc dữ liệu dạng cây, trong đó:

• Mỗi node có tối đa hai con: trái và phải.
• Tất cả các giá trị bên trái < node hiện tại.
• Tất cả các giá trị bên phải > node hiện tại.

Ý tưởng tìm kiếm:

• Bắt đầu từ root.
• Nếu key < giá trị node hiện tại → sang nhánh trái.
• Nếu key > giá trị node hiện tại → sang nhánh phải.
• Nếu bằng → tìm thấy.

Ưu điểm:

• Cho phép giữ dữ liệu ở dạng “có thứ tự” một cách linh hoạt.
• Hỗ trợ tìm kiếm, chèn, xóa trong O(h), h là chiều cao cây.

Nhược điểm:

• Nếu cây bị lệch (skew) → h ~ n → tệ như Linear Search.
• Cần thêm logic cân bằng (AVL, Red-Black Tree, v.v.).

Cây cân bằng, B-Tree và các cấu trúc nâng cao

Trong thực tế, để đảm bảo tìm kiếm luôn nhanh, người ta sử dụng:

• AVL Tree, Red-Black Tree: phiên bản BST có tự cân bằng, đảm bảo chiều cao O(log n).
• B-Tree, B+Tree: được dùng nhiều trong database, hệ thống file, nơi dữ liệu được lưu trên đĩa.

Đặc điểm chung:

• Đảm bảo thời gian tìm kiếm (lookup) O(log n).
• Phù hợp với các hệ thống cần truy vấn nhiều, dữ liệu lớn.

Tìm kiếm trong cây và đồ thị: BFS & DFS

Ngoài mảng và bảng băm, bài toán tìm kiếm còn xuất hiện rất nhiều trong cây và đồ thị. Hai thuật toán kinh điển:

• BFS (Breadth-First Search) – Duyệt theo “tầng”, đi rộng trước.
• DFS (Depth-First Search) – Duyệt sâu vào một nhánh trước rồi quay lại.

Ứng dụng:

• Tìm kiếm node thoả mãn điều kiện trong cây/đồ thị.
• Tìm đường đi, kiểm tra liên thông, phát hiện chu trình.
• Tiền xử lý cho nhiều thuật toán phức tạp khác (topo sort, SCC, v.v.).

So sánh nhanh các nhóm thuật toán tìm kiếm

• Linear Search: đơn giản, nhưng O(n) – hợp với dữ liệu nhỏ, không sắp xếp.
• Binary Search: O(log n) – cần dữ liệu đã sắp xếp.
• Hash-based Lookup: O(1) trung bình – rất mạnh để tra cứu nhanh, không quan tâm thứ tự.
• BST / Balanced Tree: O(log n) – giữ được thứ tự, hỗ trợ tìm kiếm + chèn + xóa.
• BFS / DFS: dùng cho cây/đồ thị, không tối ưu cho mảng nhưng lại là xương sống của rất nhiều thuật toán graph.

Ứng dụng thực tế

• Search box trong ứng dụng: kết hợp Binary Search, index, prefix tree (trie)…
• Database: B-Tree, B+Tree, hash index để tối ưu truy vấn.
• Hệ thống cache: Hash Map để lookup nhanh theo key.
• Game / AI: BFS/DFS và các biến thể để tìm trạng thái, đường đi, nước đi.
• Hệ thống gợi ý / phân tích: kết hợp tìm kiếm với sort, filter, scoring…

Kết luận

Các thuật toán tìm kiếm là nền tảng cho rất nhiều bài toán trong lập trình và hệ thống. Từ những kỹ thuật cơ bản như Linear Search, Binary Search, Hash-based Lookup, BST, cho đến BFS/DFS trên đồ thị – tất cả đều xoay quanh câu hỏi: “Tìm phần tử mình cần một cách hiệu quả nhất như thế nào?”.

Khi nắm vững đặc điểm của từng thuật toán và cách tổ chức dữ liệu tương ứng, bạn có thể chọn được giải pháp phù hợp cho từng bài toán cụ thể – cân bằng giữa độ phức tạp, hiệu năng và độ đơn giản của implementation.