การค้นหาเชิงเส้น (Linear Search) แบบเข้าใจง่ายจากศูนย์
บทเรียนนี้เรียงจากง่ายไปยากสำหรับผู้เริ่มต้น พร้อมตัวอย่างชีวิตจริง, ตัวอย่างข้อมูลทีละขั้น, โค้ดใช้งานได้จริง และแบบฝึกหัดท้ายบท
1) เกริ่นนำว่า การค้นหาเชิงเส้น (Linear Search) คืออะไร
การค้นหาเชิงเส้น (Linear Search) คือวิธีค้นหาข้อมูลแบบไล่ตรวจสมาชิกทีละตัว จากตำแหน่งแรกไปตำแหน่งสุดท้าย จนกว่าจะเจอค่าที่ต้องการหรือหมดข้อมูล
จุดเด่นคือเข้าใจง่ายมากและใช้ได้ทันทีแม้ข้อมูลยังไม่เรียงลำดับ
2) เปรียบเทียบกับสถานการณ์ในชีวิตจริง
ลองนึกภาพว่าเราหาชื่อในรายชื่อนักเรียนที่เขียนบนกระดาษ เราจะอ่านชื่อจากบรรทัดแรกลงไปทีละบรรทัด นี่คือแนวคิดเดียวกับ การค้นหาเชิงเส้น (Linear Search)
ถ้าเจอชื่อที่ต้องการก็หยุดทันที ถ้าอ่านครบแล้วยังไม่เจอแปลว่าไม่มีข้อมูลนั้น
3) หลักการทำงาน
หลักการมี 3 อย่าง: (1) เริ่มตรวจจากตัวแรก (2) เปรียบเทียบค่าปัจจุบันกับเป้าหมาย (3) ถ้าไม่ตรงให้เลื่อนไปตัวถัดไปจนกว่าจะจบลิสต์
4) ขั้นตอนการค้นหาทีละลำดับ
ขั้นที่ 1
ตั้งตัวชี้ (index) ไว้ที่ตำแหน่งแรกของอาเรย์
ขั้นที่ 2
เปรียบเทียบค่าที่ตำแหน่งปัจจุบันกับค่าเป้าหมาย
ขั้นที่ 3
ถ้าไม่เจอ ให้เลื่อนไปตำแหน่งถัดไปและทำซ้ำ
5) ตัวอย่างการทำงานกับ array [4, 9, 2, 7, 5] ค้นหาเลข 7
เราจะไล่จากซ้ายไปขวา: 4 → 9 → 2 → 7 → 5
กำลังเปรียบเทียบค่าทีละตัว
6) อธิบายทีละรอบว่าตรวจค่าไหนบ้าง
รอบที่ 1: ตรวจค่า 4 (ไม่ใช่ 7)
รอบที่ 2: ตรวจค่า 9 (ไม่ใช่ 7)
รอบที่ 3: ตรวจค่า 2 (ไม่ใช่ 7)
รอบที่ 4: ตรวจค่า 7 (ตรงกับเป้าหมาย) จึงหยุดและคืนตำแหน่ง 3
7) Pseudocode
โครงคิดก่อนเขียนโค้ดจริง
8) ตัวอย่างโค้ด JavaScript พร้อมคำอธิบายทีละบรรทัด
คืนตำแหน่ง (index) ของค่าที่ค้นหา ถ้าไม่เจอคืน -1
บรรทัด `for (...)` ใช้วนเช็กทุกสมาชิก, บรรทัด `if (...)` ใช้เปรียบเทียบค่าปัจจุบัน, `return i` ใช้จบทันทีเมื่อเจอ, และ `return -1` ใช้บอกว่าไม่พบข้อมูล
9) ถ้าหาเจอจะคืนค่าอะไร ถ้าไม่เจอจะคืนค่าอะไร
รูปแบบที่นิยมที่สุดคือ “เจอแล้วคืนตำแหน่ง (index)” และ “ไม่เจอคืน -1” เพราะอ่านง่ายและใช้งานต่อได้สะดวก
10) เวลาเชิงเวลา (Time Complexity): Best / Average / Worst
Best case: O(1)
เจอเป้าหมายตั้งแต่ตัวแรก
Average case: O(n)
โดยเฉลี่ยต้องตรวจหลายตำแหน่งก่อนเจอ
Worst case: O(n)
ไม่เจอเลย หรือเจอที่ตำแหน่งสุดท้าย
11) พื้นที่หน่วยความจำ (Space Complexity)
แบบ iterative ใช้ตัวแปรเพิ่มเพียงไม่กี่ตัว จึงเป็น O(1)
12) ข้อดี
- เขียนง่ายมาก เหมาะกับผู้เริ่มต้น
- ใช้ได้ทันทีแม้ข้อมูลยังไม่เรียงลำดับ
- ใช้หน่วยความจำเพิ่มน้อย
13) ข้อเสีย
- ช้าเมื่อข้อมูลมีขนาดใหญ่มาก
- ถ้าต้องค้นหาบ่อย ๆ ต้นทุนรวมจะสูง
14) เหมาะกับกรณีแบบไหน
- ข้อมูลยังไม่เรียง และไม่อยากเสียเวลาจัดเรียงก่อน
- จำนวนข้อมูลไม่มาก
- ค้นหาไม่ถี่มาก
15) ไม่เหมาะกับกรณีแบบไหน
- ข้อมูลใหญ่มากและต้องค้นหาซ้ำหลายครั้ง
- ข้อมูลเรียงแล้วและต้องการความเร็วสูง (ควรพิจารณา Binary Search)
16) เปรียบเทียบสั้น ๆ กับการค้นหาแบบทวิภาค (Binary Search)
การค้นหาเชิงเส้น (Linear Search)
ใช้กับข้อมูลทั่วไป ไม่ต้องเรียงก่อน แต่ความเร็วเฉลี่ยช้ากว่า
การค้นหาแบบทวิภาค (Binary Search)
ต้องใช้ข้อมูลเรียงลำดับก่อน แต่ค้นหาได้เร็วกว่าในข้อมูลขนาดใหญ่
17) สรุปท้ายบทแบบจำง่าย
จำสั้น ๆ: “ไล่ดูทีละตัวจากซ้ายไปขวา เจอแล้วหยุด ไม่เจอคืน -1” นี่คือแกนของการค้นหาเชิงเส้น (Linear Search)
18) แบบฝึกหัด 3 ข้อ พร้อมแนวเฉลย
ข้อ 1
เขียนฟังก์ชันหาตำแหน่งของเลข 12 ในอาเรย์ `[3, 8, 12, 1]`
แนวเฉลย: วนเช็กทีละตำแหน่ง ถ้าเจอ 12 ให้คืน index 2
ข้อ 2
ถ้าอาเรย์คือ `[5, 2, 9]` และค้นหา 7 ควรคืนค่าอะไร
แนวเฉลย: ตรวจครบแล้วยังไม่เจอ จึงคืน -1
ข้อ 3
อธิบายว่าทำไมข้อมูลขนาดใหญ่มากที่ค้นหาบ่อยอาจไม่เหมาะกับ Linear Search
แนวเฉลย: เพราะเวลาเฉลี่ยและแย่สุดเป็น O(n) จึงช้าเมื่อ n ใหญ่และเรียกซ้ำบ่อย
ถ้าต้องการฝึกแบบลงมือเขียนและตรวจผลทันที ให้ไปทำ Linear Search Lab ซึ่งมี runtime checks ครบทั้ง 3 โจทย์