Một số thuật toán tìm kiếm

Có nhiều cách để tìm một phần tử trong dữ liệu. Mỗi thuật toán có ưu điểm và nhược điểm riêng. Tùy vào dữ liệu mà chúng ta chọn thuật toán phù hợp.

1. Linear Search (Tìm kiếm tuần tự)

Ý tưởng:

Kiểm tra từng phần tử từ đầu đến cuối cho đến khi tìm thấy.

Ví dụ:

a = [12, 5, 31, 18, 7]
x = 18
for i in range(len(a)):
    if a[i] == x:
        print("Tìm thấy tại vị trí", i)
        break

Ưu điểm

• Không cần sắp xếp dữ liệu.
• Dễ hiểu, dễ lập trình.

Nhược điểm

• Chậm khi dữ liệu lớn.

Độ phức tạp:

O(n)

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

Ý tưởng:

Luôn kiểm tra phần tử ở giữa danh sách.
Nếu giá trị cần tìm lớn hơn phần tử giữa thì bỏ nửa bên trái.
Nếu nhỏ hơn thì bỏ nửa bên phải.

Ví dụ:

3 7 9 12 18 25 31 40
        ↑

Tìm số 31

31 > 18

Bỏ nửa bên trái.

Độ phức tạp:

O(log n)

Điều kiện:

• Dữ liệu phải được sắp xếp.

3. Jump Search

Ý tưởng:

Không tìm từng phần tử mà nhảy từng đoạn.

Ví dụ:

1  2  3 [4]
5  6  7 [8]
9 10 11 [12]
13 14 15 [16]

Tìm số 10

Kiểm tra 4
↓
Kiểm tra 8
↓
Kiểm tra 12
↓
Biết 10 nằm giữa 8 và 12
↓
Tìm tuần tự trong đoạn đó.

Độ phức tạp:

O(√n)

4. Interpolation Search

Ý tưởng:

Thay vì luôn chọn phần tử ở giữa, thuật toán sẽ dự đoán vị trí của giá trị cần tìm.

Ví dụ:

10 20 30 40 50 60 70 80 90

Tìm số 80

Binary Search sẽ kiểm tra giữa trước.

Interpolation Search sẽ đoán gần cuối dãy nên thường nhanh hơn nếu dữ liệu phân bố đều.

Độ phức tạp trung bình:

O(log log n)

5. Tree Search (Tìm kiếm trên cây)

Ý tưởng:

Áp dụng khi dữ liệu được lưu dưới dạng cây nhị phân tìm kiếm (Binary Search Tree).

Ví dụ:

        20
      /    \
    10      35
   /  \    /  \
  5   15 30   40

Tìm số 30

20

↓

35

↓

30

Độ phức tạp:

O(log n)

(Nếu cây cân bằng.)

6. Hash Search (Hash Table)

Ý tưởng:

Lưu dữ liệu theo khóa (key), giúp tra cứu gần như ngay lập tức.

Ví dụ:

hoc_sinh = {
    "An": 9,
    "Bình": 8,
    "Lan": 10
}

print(hoc_sinh["Lan"])

Độ phức tạp trung bình:

O(1)

7. Tìm kiếm bằng Set

Python sử dụng Hash Table cho kiểu dữ liệu Set.

s = {5, 12, 18, 30}

if 18 in s:
    print("Có")

Độ phức tạp trung bình:

O(1)

8. Toán tử in

Ví dụ:

a = [5, 8, 10, 13]

print(10 in a)

Kết quả:

True

Nếu dữ liệu là List thì Python sẽ tìm tuần tự.

Nếu dữ liệu là Set hoặc Dictionary thì Python sẽ dùng Hash Search.

9. Hàm index()

Ví dụ:

a = [5, 8, 10, 13]

print(a.index(10))

Kết quả:

2

Bên trong, hàm index() cũng sử dụng Linear Search.

10. Bảng so sánh các thuật toán tìm kiếm

11. Kinh nghiệm, nên học theo thứ tự

1. Linear Search
2. Binary Search
3. Hash Search (Dictionary, Set)
4. Tree Search
5. Jump Search
6. Interpolation Search

12. Kết luận

• ✔ Linear Search: đơn giản, không cần sắp xếp dữ liệu.
• ✔ Binary Search: nhanh, nhưng yêu cầu dữ liệu đã sắp xếp.
• ✔ Hash Search: nhanh nhất trong đa số trường hợp tra cứu theo khóa.
• ✔ Tree Search: dùng cho cấu trúc dữ liệu dạng cây.
• ✔ Jump Search và Interpolation Search: ít dùng hơn nhưng hữu ích trong một số bài toán đặc biệt.