Menu Học Tập

Bài 19: Bài toán tìm kiếm – Tin học 11 | Lý thuyết

Mục lục [Ẩn]

Chọn đến phần học sinh cần nhanh chóng thông qua mục lục bằng cách click đến phần đó

I. Lý thuyết trọng tâm

1. Bài toán tìm kiếm trên thực tế

Tìm kiếm là một trong những bài toán nền tảng và quan trọng bậc nhất của Tin học. Trong cuộc sống hằng ngày, ta liên tục gặp các tình huống tìm kiếm: tìm một tệp trên máy tính, tìm hình ảnh trên Internet, tìm học sinh đạt điểm cao nhất trong bảng điểm,…

Mỗi bài toán tìm kiếm đều có hai thành phần cốt lõi:

  • Miền dữ liệu: Tập hợp tất cả các đối tượng mà ta cần tìm trong đó (ví dụ: tất cả ảnh trên Internet, tất cả tệp trên ổ cứng, danh sách học sinh,…).
  • Kết quả (nghiệm): Đối tượng thoả mãn tiêu chí tìm kiếm (ví dụ: ảnh hoa hồng, tệp có tên cụ thể, 5 học sinh điểm cao nhất,…).

Cách thiết kế thuật toán tìm kiếm phụ thuộc vào cấu trúc của miền dữ liệu và tiêu chí cụ thể của bài toán. Trong phạm vi bài học này, ta xét bài toán tìm kiếm trên mô hình dữ liệu đơn giản nhất: một dãy số (mảng một chiều).

Phát biểu bài toán:

  • Đầu vào: Dãy số A gồm n phần tử A[0], A[1], …, A[n−1] và một giá trị K cần tìm.
  • Đầu ra: Chỉ số i sao cho A[i] = K. Nếu không tồn tại phần tử nào bằng K, trả về −1.

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

2.1. Ý tưởng thuật toán

Tìm kiếm tuần tự là cách tiếp cận đơn giản và trực quan nhất: duyệt lần lượt từng phần tử của dãy từ đầu đến cuối (hoặc từ cuối về đầu), so sánh mỗi phần tử với giá trị K. Nếu tìm thấy phần tử bằng K thì trả về chỉ số tương ứng; nếu duyệt hết mà không tìm thấy thì trả về −1.

Thuật toán này không yêu cầu dãy phải được sắp xếp trước – nó hoạt động đúng trên mọi dãy số.

2.2. Minh hoạ từng bước

Xét dãy A = [1, 4, 7, 8, 3, 9, 10], cần tìm K = 9.

Bước Chỉ số i Giá trị A[i] So sánh với K = 9
1 0 1 1 ≠ 9 → tiếp tục
2 1 4 4 ≠ 9 → tiếp tục
3 2 7 7 ≠ 9 → tiếp tục
4 3 8 8 ≠ 9 → tiếp tục
5 4 3 3 ≠ 9 → tiếp tục
6 5 9 9 = 9 → tìm thấy tại chỉ số 5

Thuật toán duyệt qua 6 phần tử mới tìm được kết quả.

2.3. Cài đặt bằng Python

def LinearSearch(A, K):
    for i in range(len(A)):
        if A[i] == K:
            return i
    return -1

Giải thích: Vòng for chạy biến i từ 0 đến len(A) - 1. Tại mỗi bước, nếu A[i] == K thì lập tức trả về i (kết thúc hàm ngay). Nếu vòng lặp kết thúc mà chưa trả về giá trị nào, nghĩa là không tìm thấy K trong dãy, hàm trả về −1.

2.4. Đánh giá thuật toán

  • Trường hợp tốt nhất: Phần tử cần tìm nằm ngay ở vị trí đầu tiên → chỉ cần 1 bước.
  • Trường hợp xấu nhất: Phần tử cần tìm nằm ở vị trí cuối cùng hoặc không có trong dãy → phải duyệt hết n phần tử.
  • Ưu điểm: Đơn giản, dễ cài đặt, áp dụng cho mọi dãy (không cần sắp xếp).
  • Nhược điểm: Chậm khi dãy có nhiều phần tử, vì trong trường hợp xấu nhất phải duyệt toàn bộ.

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

3.1. Điều kiện áp dụng

Khác với tìm kiếm tuần tự, tìm kiếm nhị phân chỉ áp dụng được khi dãy đã được sắp xếp theo thứ tự xác định (tăng dần hoặc giảm dần). Đổi lại, nó cho tốc độ tìm kiếm nhanh hơn rất nhiều.

3.2. Ý tưởng thuật toán

Ý tưởng cốt lõi là liên tục thu hẹp phạm vi tìm kiếm đi một nửa sau mỗi bước:

  • Xác định phạm vi tìm kiếm ban đầu bằng hai biến: left (chỉ số đầu) và right (chỉ số cuối). Ban đầu left = 0, right = n − 1.
  • Tính chỉ số phần tử giữa: mid = (left + right) // 2.
  • So sánh K với A[mid], xảy ra một trong ba trường hợp:
    • Nếu K = A[mid]: Tìm thấy → trả về mid.
    • Nếu K < A[mid]: Phần tử cần tìm nằm ở nửa trái → cập nhật right = mid − 1.
    • Nếu K > A[mid]: Phần tử cần tìm nằm ở nửa phải → cập nhật left = mid + 1.
  • Lặp lại cho đến khi tìm thấy hoặc phạm vi rỗng (left > right).

3.3. Minh hoạ từng bước

Xét dãy đã sắp xếp A = [1, 3, 4, 7, 8, 9, 10], cần tìm K = 9.

Bước 1: Phạm vi tìm kiếm: toàn bộ dãy (chỉ số 0 → 6).

left = 0, right = 6
mid = (0 + 6) // 2 = 3
A[3] = 7 < K = 9  →  phần tử cần tìm nằm ở nửa phải
Cập nhật: left = 3 + 1 = 4

Bước 2: Phạm vi tìm kiếm: chỉ số 4 → 6 (tức các phần tử [8, 9, 10]).

left = 4, right = 6
mid = (4 + 6) // 2 = 5
A[5] = 9 = K = 9  →  tìm thấy tại chỉ số 5. Kết thúc.

So sánh: Với cùng dãy 7 phần tử và cùng giá trị K = 9, tìm kiếm tuần tự cần 6 bước trong khi tìm kiếm nhị phân chỉ cần 2 bước. Sự khác biệt sẽ càng lớn khi dãy có nhiều phần tử hơn.

3.4. Cài đặt bằng Python

def BinarySearch(A, K):
    left = 0
    right = len(A) - 1
    while left <= right:
        mid = (left + right) // 2
        if A[mid] == K:
            return mid
        elif A[mid] < K:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Giải thích: Vòng while tiếp tục chạy khi phạm vi tìm kiếm chưa rỗng (left <= right). Mỗi lần lặp, phạm vi giảm đi khoảng một nửa nhờ cập nhật left hoặc right. Nếu thoát vòng lặp mà chưa return mid, nghĩa là K không có trong dãy → trả về −1.

3.5. Đánh giá thuật toán

  • Trường hợp tốt nhất: Phần tử cần tìm nằm ngay giữa dãy → chỉ cần 1 bước.
  • Trường hợp xấu nhất: Với dãy n phần tử, số bước tối đa xấp xỉ log₂(n). Ví dụ: dãy 1.000.000 phần tử chỉ cần tối đa khoảng 20 bước.
  • Ưu điểm: Cực kỳ nhanh trên dãy lớn đã sắp xếp.
  • Nhược điểm: Yêu cầu bắt buộc dãy phải được sắp xếp trước.

4. So sánh hai thuật toán

Tiêu chí Tìm kiếm tuần tự Tìm kiếm nhị phân
Yêu cầu dữ liệu Không cần sắp xếp Bắt buộc đã sắp xếp
Cách hoạt động Duyệt lần lượt từng phần tử Thu hẹp phạm vi đi một nửa mỗi bước
Số bước (xấu nhất) n ≈ log₂(n)
Ví dụ: n = 1.000.000 Tối đa 1.000.000 bước Tối đa ≈ 20 bước
Khi nào nên dùng Dãy nhỏ hoặc chưa sắp xếp Dãy lớn đã sắp xếp

II. Phương pháp giải các dạng bài tập

Dạng 1: Chỉnh sửa thuật toán tìm kiếm tuần tự

Phương pháp: Thuật toán mẫu chỉ tìm một phần tử đầu tiên bằng K rồi dừng. Để tìm tất cả phần tử bằng K, thay vì return i ngay khi tìm thấy, ta lưu chỉ số vào một danh sách kết quả và tiếp tục duyệt đến hết dãy.

Bài 1 (Luyện tập SGK). Em hãy chỉnh sửa thuật toán tìm kiếm tuần tự để tìm ra tất cả các phần tử trong dãy bằng giá trị cần tìm, biết dãy đó có nhiều phần tử bằng giá trị cần tìm.

Lời giải:

def LinearSearchAll(A, K):
    ket_qua = []
    for i in range(len(A)):
        if A[i] == K:
            ket_qua.append(i)
    return ket_qua

# Thử nghiệm
A = [3, 7, 2, 9, 7, 5, 7, 1]
K = 7
ds = LinearSearchAll(A, K)
if len(ds) == 0:
    print("Không tìm thấy")
else:
    print(f"Tìm thấy {K} tại các chỉ số:", ds)

Giải thích: Khác biệt quan trọng so với bản gốc: thay vì return i ngay, ta dùng ket_qua.append(i) để ghi nhận vị trí rồi tiếp tục duyệt. Chỉ sau khi vòng for kết thúc mới trả về danh sách tất cả chỉ số tìm được. Nếu danh sách rỗng nghĩa là không tìm thấy.

Dạng 2: Viết tìm kiếm nhị phân cho dãy giảm dần

Phương pháp: Với dãy giảm dần, logic so sánh bị đảo ngược so với dãy tăng dần. Nếu K < A[mid], phần tử cần tìm nằm ở nửa phải (vì các phần tử bên phải nhỏ hơn). Nếu K > A[mid], phần tử cần tìm nằm ở nửa trái.

Bài 2 (Luyện tập SGK). Viết chương trình của thuật toán tìm kiếm nhị phân với dãy sắp xếp giảm dần.

Lời giải:

def BinarySearchDesc(A, K):
    left = 0
    right = len(A) - 1
    while left <= right:
        mid = (left + right) // 2
        if A[mid] == K:
            return mid
        elif A[mid] > K:       # Đảo chiều: A[mid] lớn hơn K → tìm bên phải
            left = mid + 1
        else:                   # A[mid] < K → tìm bên trái
            right = mid - 1
    return -1

# Thử nghiệm
A = [67, 34, 31, 20, 18, 17, 14, 12, 10, 9, 4, 0]
K = 34
vi_tri = BinarySearchDesc(A, K)
if vi_tri == -1:
    print("Không tìm thấy")
else:
    print(f"Tìm thấy {K} tại chỉ số {vi_tri}")

Giải thích: Cấu trúc thuật toán giữ nguyên, chỉ đổi chiều so sánh ở nhánh elif và else. Trong dãy giảm dần, phần tử bên trái lớn hơn, bên phải nhỏ hơn – nên khi A[mid] > K, giá trị K phải nằm ở phía bên phải (phần nhỏ hơn), ta cập nhật left = mid + 1. Ngược lại khi A[mid] < K, ta tìm bên trái.

Dạng 3: Tìm kiếm trên danh sách tên (dữ liệu xâu kí tự)

Phương pháp: Thuật toán tìm kiếm không chỉ áp dụng cho số mà còn cho xâu kí tự. Trong Python, toán tử ==, <, > hoạt động trên xâu theo thứ tự bảng chữ cái (thứ tự từ điển), nên cả tìm kiếm tuần tự lẫn nhị phân đều áp dụng được cho danh sách tên.

Bài 3 (Vận dụng SGK). Cho A là danh sách tên các học sinh trong lớp, viết chương trình tìm kiếm tuần tự để tìm ra các học sinh có tên là “Hoàn”.

Lời giải:

def TimTenTuanTu(A, ten_can_tim):
    ket_qua = []
    for i in range(len(A)):
        if A[i] == ten_can_tim:
            ket_qua.append(i)
    return ket_qua

# Thử nghiệm
A = ["An", "Bình", "Hoàn", "Dũng", "Hoàn", "Lan", "Mai", "Hoàn"]
ds = TimTenTuanTu(A, "Hoàn")
if len(ds) == 0:
    print("Không tìm thấy học sinh tên Hoàn")
else:
    print(f"Tìm thấy {len(ds)} học sinh tên Hoàn tại các vị trí (tính từ 1):")
    for vt in ds:
        print(f"  Vị trí {vt + 1}")

Giải thích: Vì có thể có nhiều học sinh trùng tên, ta dùng phiên bản tìm kiếm tuần tự tìm tất cả (tương tự Bài 1 Luyện tập). So sánh A[i] == ten_can_tim hoạt động đúng với xâu kí tự trong Python.

Bài 4 (Vận dụng SGK). Cho A là danh sách tên các học sinh trong lớp đã được sắp xếp theo thứ tự bảng chữ cái, viết chương trình tìm kiếm nhị phân để tìm ra các học sinh có tên là “Minh”.

Lời giải:

def TimTenNhiPhan(A, ten_can_tim):
    left = 0
    right = len(A) - 1
    while left <= right:
        mid = (left + right) // 2
        if A[mid] == ten_can_tim:
            # Tìm thấy 1 vị trí, mở rộng sang 2 bên để tìm thêm (vì có thể trùng tên)
            ket_qua = [mid]
            # Mở rộng sang trái
            i = mid - 1
            while i >= 0 and A[i] == ten_can_tim:
                ket_qua.append(i)
                i -= 1
            # Mở rộng sang phải
            j = mid + 1
            while j < len(A) and A[j] == ten_can_tim:
                ket_qua.append(j)
                j += 1
            ket_qua.sort()
            return ket_qua
        elif A[mid] < ten_can_tim:
            left = mid + 1
        else:
            right = mid - 1
    return []

# Thử nghiệm
A = ["An", "Bình", "Dũng", "Hoàn", "Lan", "Minh", "Minh", "Nam", "Tuấn"]
ds = TimTenNhiPhan(A, "Minh")
if len(ds) == 0:
    print("Không tìm thấy học sinh tên Minh")
else:
    print(f"Tìm thấy {len(ds)} học sinh tên Minh tại các vị trí (tính từ 1):")
    for vt in ds:
        print(f"  Vị trí {vt + 1}")

Giải thích: Vì dãy đã sắp xếp theo bảng chữ cái, toán tử <, > trên xâu so sánh theo thứ tự từ điển – hoàn toàn phù hợp cho tìm kiếm nhị phân. Điểm đặc biệt: sau khi nhị phân tìm được một vị trí có tên “Minh”, ta cần mở rộng sang trái và phải để tìm thêm các vị trí trùng tên (vì trong dãy đã sắp, các tên giống nhau sẽ nằm liền kề).

III. Sơ đồ tư duy

                          ┌─ Miền dữ liệu: tập hợp cần tìm trong đó
  ┌─ Bài toán tìm kiếm ──┤
  │                       └─ Kết quả: phần tử thoả tiêu chí
  │
  │                       ┌─ Ý tưởng: duyệt lần lượt từ đầu đến cuối
  │                       ├─ Không cần sắp xếp
  ├─ Tìm kiếm tuần tự ───┼─ Tốt nhất: 1 bước (ở đầu dãy)
  │     (Linear Search)   ├─ Xấu nhất: n bước (ở cuối hoặc không có)
  │                       └─ Code: for i → if A[i]==K → return i
  │
  │                       ┌─ Điều kiện: dãy ĐÃ SẮP XẾP
  │                       ├─ Ý tưởng: thu hẹp phạm vi 1/2 mỗi bước
  └─ Tìm kiếm nhị phân ──┼─ So sánh K với A[mid]:
      (Binary Search)     │    K = A[mid] → tìm thấy
                          │    K < A[mid] → tìm nửa trái
                          │    K > A[mid] → tìm nửa phải
                          ├─ Xấu nhất: ≈ log₂(n) bước
                          └─ Code: while left<=right → mid → so sánh
Thầy Phạm Thành Danh

Thầy Phạm Thành Danh

(Người kiểm duyệt, ra đề)

Chức vụ: Trưởng ban biên soạn môn Tin Học THPT

Trình độ: Cử nhân Sư phạm Tin học, Chứng chỉ hạng II, Chứng chỉ Tin học, Ngoại ngữ B1

Kinh nghiệm: 8+ năm kinh nghiệm tại Trường THPT Thuận Hóa

Bài 31: Thực hành thiết lập thư viện chương trình ( 10/02 )

Bài 30: Thiết lập thư viện cho chương trình – Lý thuyết ( 10/02 )

Bài 29: Thực hành thiết kế chương trình theo mô đun ( 10/02 )

Bài 28: Thiết kế chương trình theo mô đun – Lý thuyết ( 10/02 )

Bài 27: Thực hành thiết kế chương trình theo phương pháp làm mịn dần ( 10/02 )