Thuật toán C/C++

Tìm kiếm tuyến tính trong C, C++

Trong bài học này, bạn sẽ tìm vị trí của một giá trị trong mảng chưa sắp xếp bằng thuật toán tìm kiếm tuyến tính.

Giới thiệu

Tìm kiếm tuyến tính kiểm tra lần lượt từng phần tử từ đầu mảng cho đến khi tìm thấy giá trị cần tìm hoặc đã duyệt hết mảng. Đây là thuật toán tìm kiếm đơn giản nhất và hoạt động được cả khi dữ liệu chưa được sắp xếp.

Những điểm quan trọng

Kiểm thử với dữ liệu rỗng, chỉ có một phần tử, có giá trị trùng và đã được sắp xếp.
Viết cho đúng trước, tối ưu sau.
Trong code thực tế, ưu tiên dùng các hàm có sẵn của thư viện chuẩn.

Mô phỏng Tìm kiếm tuyến tính trong C, C++

O(n)

Nhấn Phát hoặc Từng bước để theo dõi từng phép so sánh và thay đổi dữ liệu.

Code ví dụ bằng C và C++

Chạy code →

main.c

#include <stdio.h>

int find(const int *values, int size, int target) {
    for (int index = 0; index < size; ++index) {
        if (values[index] == target) return index;
    }
    return -1;
}

int main(void) {
    int values[] = {14, 3, 27, 8, 19};
    printf("index=%d\n", find(values, 5, 8));
}

Kết quả khi chạy

index=3

C++

Chạy code →

main.cpp

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector values{14, 3, 27, 8, 19};
    auto match = std::find(values.begin(), values.end(), 8);
    std::cout << "index="
              << std::distance(values.begin(), match) << '\n';
}

Kết quả khi chạy

index=3

So sánh C và C++

Cả hai phiên bản đều có độ phức tạp O(n) trong trường hợp xấu nhất. Hàm find trong C trả về chỉ số kiểu int có dấu, nhờ đó có thể dùng -1 để báo không tìm thấy. Phiên bản C++ dùng std::find, hàm này trả về một iterator, và nếu iterator bằng values.end() nghĩa là giá trị không có trong mảng.

Vòng lặp, con trỏ, độ dài và vùng nhớ tạm đều được viết tường minh.

C++

Iterator và các thuật toán chuẩn tách thao tác xử lý khỏi cách dữ liệu được lưu trữ.

Bài tập mở rộng

Hãy chạy cả hai phiên bản, sau đó thử thay đổi code để quan sát sự khác biệt về mức độ an toàn mà mỗi ngôn ngữ mang lại.

Tự mô phỏng từng phép so sánh trên giấy.
Thử với giá trị trùng lặp và các giá trị cực lớn, cực nhỏ.
Đo thời gian chạy của code tự viết và so sánh với thư viện chuẩn.

Luyện tập với thử thách

Áp dụng kiến thức của bài học này để giải một bài toán thực tế. Mỗi thử thách chạy ngay trên trình duyệt, có kiểm thử tức thì và AI nhận xét.

First Negative Index Find where the first negative number appears. Dễ

Tất cả thử thách