อัลกอริทึม C/C++

Linear Search

Linear search ตรวจทีละ element จนพบหรือถึงท้าย

Linear Search คืออะไร?

Linear search ตรวจทีละ element จนพบหรือถึงท้าย

หา target ในข้อมูลที่ยังไม่เรียง

ประเด็นสำคัญ

  • ทดสอบ input ว่าง หนึ่งสมาชิก ซ้ำ และเรียงแล้ว
  • แยก correctness จาก optimization
  • ใช้ standard library ใน production เมื่อเหมาะสม

ภาพจำลอง Linear Search

O(n)

กด เล่น หรือ ทีละขั้น เพื่อดูการเปรียบเทียบและการย้ายข้อมูลแต่ละขั้น

ตัวอย่างโค้ด C และ C++

C
รันโค้ด →
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));
}
ผลลัพธ์ที่คาดหวัง
index=3
C++
รันโค้ด →
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';
}
ผลลัพธ์ที่คาดหวัง
index=3

เปรียบเทียบ C และ C++

ทั้งสองแบบ worst-case O(n) C คืน -1 ส่วน C++ คืน iterator แล้วเทียบ end

C

Loop, pointer, length และ buffer เขียนอย่างชัดเจน

C++

Iterator และ algorithm แยก operation จาก storage

แบบฝึกหัด

รันทั้งสองเวอร์ชันแล้วแก้ไขเพื่อสังเกตความแตกต่างของภาษา

  • ไล่ตามทุก comparison
  • ทดสอบ duplicate และ extreme value
  • Benchmark กับ standard library