🔍
Thuật Toán
Chapter 7 · Lưu Đồ & Thuật Toán
Thuật Toán
Tìm Kiếm
Linear Search và Binary Search — hiểu rõ sự khác biệt về hiệu quả và khi nào áp dụng từng thuật toán!
Phần 1 — Linear Search (Tìm kiếm tuần tự)
Duyệt từng phần tử từ đầu đến cuối
Ý tưởng đơn giản nhất: kiểm tra lần lượt từng phần tử trong mảng cho đến khi tìm thấy phần tử cần tìm hoặc duyệt hết mảng mà không tìm thấy.
Tìm X=7 trong mảng [3, 9, 2, 7, 5, 1, 8]:
3
0
9
1
2
2
7
3✓
5
4
1
5
8
6
i=0: A[0]=3, 3≠7Bỏ qua
i=1: A[1]=9, 9≠7Bỏ qua
i=2: A[2]=2, 2≠7Bỏ qua
i=3: A[3]=7, 7=7 → TÌM THẤY tại vị trí 3!Found!
FOR i = 0 TO n-1 DO
IF A[i] = X THEN
In "Tìm thấy tại ", i
STOP
In "Không tìm thấy"
| i | A[i] | A[i]=7? | Kết quả |
|---|---|---|---|
| 0 | 3 | ✗ | Tiếp tục |
| 1 | 9 | ✗ | Tiếp tục |
| 2 | 2 | ✗ | Tiếp tục |
| 3 | 7 | ✓ | Vị trí 3 ✅ |
📊 Độ phức tạp: Tốt nhất O(1) — tìm ngay vị trí 0. Tệ nhất O(n) — phần tử ở cuối hoặc không tồn tại.
Phần 2 — Binary Search (Tìm kiếm nhị phân)
Chia đôi không gian tìm kiếm mỗi bước — cực nhanh!
Điều kiện bắt buộc: Mảng phải được sắp xếp trước! Mỗi bước, so sánh X với phần tử giữa (mid) rồi loại bỏ nửa mảng không chứa X.
Tìm X=14 trong mảng đã sắp xếp [2, 5, 8, 12, 14, 23, 31, 38]:
Bước 1: left=0, right=7 → mid=3, A[3]=12 < 14 → tìm bên phải
2
0
loại
5
1
loại
8
2
loại
12
3
mid
14
4
→ tìm
23
5
31
6
38
7
Bước 2: left=4, right=7 → mid=5, A[5]=23 > 14 → tìm bên trái
2
0
5
1
8
2
12
3
14
4
✓ Found!
23
5
mid
31
6
38
7
L = 0; R = n-1; tim = false
WHILE L ≤ R AND NOT tim DO
mid = (L + R) / 2
IF A[mid] = X THEN
tim = true; vt = mid
ELSE IF A[mid] < X THEN
L = mid + 1 ← tìm bên phải
ELSE
R = mid - 1 ← tìm bên trái
IF tim THEN In "Tìm thấy tại vt"
ELSE In "Không tìm thấy"
| Bước | L | R | mid | A[mid] | So sánh |
|---|---|---|---|---|---|
| 1 | 0 | 7 | 3 | 12 | 12<14→L=4 |
| 2 | 4 | 7 | 5 | 23 | 23>14→R=4 |
| 3 | 4 | 4 | 4 | 14 | 14=14 ✅ |
⚡ Chỉ 3 bước cho mảng 8 phần tử! Nếu Linear Search phải kiểm tra 5 lần, Binary Search chỉ cần 3 lần. Với mảng 1.000.000 phần tử: Binary Search tối đa chỉ cần 20 bước!
Phần 3 — So sánh Linear vs Binary Search
Khi nào dùng thuật toán nào?
🚶 Linear Search
- Mảng chưa sắp xếp
- Mảng nhỏ (n < 20)
- Độ phức tạp O(n)
- Đơn giản, dễ cài đặt
- Tìm được trên mọi kiểu dữ liệu
⚡ Binary Search
- Mảng đã sắp xếp — BẮT BUỘC!
- Mảng lớn (n > 100)
- Độ phức tạp O(log n)
- Cực nhanh với mảng lớn
- Phải sắp xếp trước nếu cần
📊 So sánh thực tế — Tìm trong 1.000.000 phần tử:
🚶 Linear Search: Tệ nhất = 1.000.000 lần so sánh
⚡ Binary Search: Tệ nhất = log₂(1.000.000) ≈ 20 lần so sánh!
🚶 Linear Search: Tệ nhất = 1.000.000 lần so sánh
⚡ Binary Search: Tệ nhất = log₂(1.000.000) ≈ 20 lần so sánh!
🧩 Kiểm tra nhanh!
Chapter 7 — Thuật toán tìm kiếm
Binary Search yêu cầu điều kiện gì?
→ Mảng phải được sắp xếp trước
→ Mảng phải được sắp xếp trước
Tìm mid trong Binary Search tính thế nào?
→ mid = (L + R) / 2
→ mid = (L + R) / 2
A[mid] > X thì cập nhật biến nào?
→ R = mid - 1 (tìm bên trái)
→ R = mid - 1 (tìm bên trái)
Tìm 9 trong [1,3,5,7,9,11]: cần mấy bước nhị phân?
→ 2 bước: mid=3→7, mid=4→9 ✅
→ 2 bước: mid=3→7, mid=4→9 ✅