Thuật toán C/C++

Tìm kiếm tuyến tính

Linear search kiểm tra lần lượt cho đến khi match hoặc hết dữ liệu.

Tìm kiếm tuyến tính là gì?

Linear search kiểm tra lần lượt cho đến khi match hoặc hết dữ liệu.

Tìm target trong dữ liệu chưa sắp xếp.

Điểm quan trọng

Test input rỗng, một phần tử, trùng lặp và đã sắp xếp.
Tách correctness khỏi optimization.
Ưu tiên standard library trong code production.

Mô phỏng Tìm kiếm tuyến tính

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));
}

Output dự kiến

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';
}

Output dự kiến

index=3

So sánh C và C++

Hai bản đều có worst-case O(n). C trả signed index để dùng -1; C++ trả iterator và so với end.

Loop, pointer, length và buffer tạm được viết tường minh.

C++

Iterator và standard algorithm tách operation khỏi cách lưu dữ liệu.

Bài tập mở rộng

Chạy cả hai phiên bản rồi thay đổi để quan sát khác biệt về bảo đảm của từng ngôn ngữ.

Trace từng phép so sánh trên giấy.
Test duplicate và extreme value.
Benchmark code tự viết với standard library.