Tìm kiếm tuần tự¶

Đặt vấn đề¶

Nhu cầu về thông tin của con người là thiết yếu, trong khi lượng dữ liệu lưu trữ trên các hệ thống là rất lớn. Làm sao con người có thể truy xuất được ngay thông tin mình cần trong bể thông tin rộng lớn đó?

Bài toán và thuật toán tìm kiếm¶

Một cách tổng quát, bài toán tìm kiếm đề cập đến việc tìm một hoặc nhiều đối tượng thoả các yêu cầu cụ thể trong một tập hợp đối tượng có liên quan.

Trong bài này, phạm vi của bài toán tìm kiếm được giới hạn trong mảng một chiều và chỉ tìm một phần tử có giá trị k cho trước.

Có nhiều thuật toán tìm kiếm khác nhau ứng với các yếu tố khác nhau như: loại dữ liệu, kích thước của tập dữ liệu, cách thức tổ chức và lưu trữ dữ liệu.

Đối với bài toán vừa nêu trên, có hai thuật toán cơ bản là: tìm kiếm tuần tự và tìm kiếm nhị phân.

Bài học này chỉ đề cập thuật toán tìm kiếm tuần tự, hay còn gọi là tìm kiếm tuyến tính.

Thuật toán tìm kiếm tuần tự¶

Ý tưởng¶

Hãy tưởng tượng hình ảnh tất cả lá bài đều úp, ta tìm xem một lá 3 nút (bất kỳ trong số bốn lá 3 nút) nằm ở vị trí nào.

Cách làm là lần lượt lật từng lá bài lên cho đến khi thấy được lá 3 nút.

Áp dụng cách trên cho mảng, ta lần lượt, hoặc còn gọi là tuần tự, so sánh từng phần tử với giá trị k, bắt đầu từ phần tử đầu tiên đến phần tử cuối cùng, khi nào bắt gặp k thì dừng. Cụ thể như sau:

Lưu đồ thuật toán¶

Trực quan hóa thuật toán¶

Chương trình minh họa¶

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# Hàm tìm kiếm tuần tự
def linear_search(A, k):
    n = len(A)

    # Duyệt mảng từ vị trí đầu đến cuối, so sánh A[i] và k
    for i in range(n):
        if A[i] == k:
            return i

    # Trả về -1, không tìm thấy
    return -1


# Chương trình chính
if __name__ == '__main__':
    array = [1, 7, 4, 0, 9, 4, 8, 8, 2, 4, 5, 5]
    key = 9

    found_at = linear_search(array, key)

    if found_at == -1:
        print(f'Không tìm thấy key = {key}')
    else:
        print(f'Tìm thấy key = {key} tại vị trí {found_at}')

Output:

Tìm thấy key = 9 tại vị trí 4

Bổ sung chương trình chính để thử tìm key = 6.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

# Chương trình chính
if __name__ == '__main__':
    # ...

    key = 6

    found_at = linear_search(array, key)

    if found_at == -1:
        print(f'Không tìm thấy key = {key}')
    else:
        print(f'Tìm thấy key = {key} tại vị trí {found_at}')

Output:

Không tìm thấy key = 6

Sơ đồ tóm tắt nội dung¶

Google Colab¶

Các đoạn mã trong bài này được đặt tại Google Colab để bạn có thể thử nghiệm theo cách của riêng mình.

Some English words¶