Linear Search
Linear search ตรวจทีละ element จนพบหรือถึงท้าย
Linear Search คืออะไร?
Linear search ตรวจทีละ element จนพบหรือถึงท้าย
หา target ในข้อมูลที่ยังไม่เรียง
ประเด็นสำคัญ
- ทดสอบ input ว่าง หนึ่งสมาชิก ซ้ำ และเรียงแล้ว
- แยก correctness จาก optimization
- ใช้ standard library ใน production เมื่อเหมาะสม
ภาพจำลอง Linear Search
O(n)กด เล่น หรือ ทีละขั้น เพื่อดูการเปรียบเทียบและการย้ายข้อมูลแต่ละขั้น
ตัวอย่างโค้ด 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