Searching

รู้จัก Linear Search

Linear Search (การค้นหาเชิงเส้น) คืออัลกอริทึมสำหรับค้นหาข้อมูลที่ง่ายที่สุด — เราไล่ตรวจสมาชิกในอาเรย์ทีละตัว จากตำแหน่งแรกไปตำแหน่งสุดท้าย จนกว่าจะเจอค่าที่ต้องการ หรือตรวจครบแล้วไม่เจอ

ข้อได้เปรียบที่สำคัญที่สุดของ Linear Search คือใช้ได้ทันทีแม้ข้อมูลยังไม่เรียงลำดับ — ไม่ต้องจัดเรียงก่อน ไม่ต้องเตรียมอะไรก่อน แค่มีอาเรย์กับค่าเป้าหมายก็เริ่มค้นหาได้เลย

• ไม่ต้องเรียงข้อมูลก่อนค้นหา — ใช้ได้กับอาเรย์ทุกรูปแบบ
• ตรวจทีละตัวแบบตรงไปตรงมา — เข้าใจง่าย เขียนตามง่าย
• คืน index ของค่าที่เจอ — ถ้าไม่เจอคืน -1

แนวคิดจากชีวิตจริง

ลองนึกภาพว่าเรามีรายชื่อนักเรียนเขียนบนกระดาษ และต้องหาชื่อใครสักคน — เราจะอ่านชื่อจากบรรทัดแรกลงไปทีละบรรทัดจนกว่าจะเจอชื่อนั้น หรืออ่านหมดทั้งหน้าแล้วยังไม่เจอ นี่คือแนวคิดเดียวกับ Linear Search

ไล่ตรวจจากซ้ายไปขวาทีละตำแหน่ง — เจอเมื่อไหร่หยุดเมื่อนั้น

ในโลกโค้ด เราก็ทำแบบเดียวกัน — ใช้ loop (เช่น for) วนเช็กค่าทีละ index จนกว่าค่าตรงกับเป้าหมาย

ขั้นตอนการทำงานและ Pseudocode

• ตั้ง index เริ่มต้นที่ตำแหน่งแรกของอาเรย์ (i = 0)
• เปรียบเทียบค่า values[i] กับค่าเป้าหมาย (target)
• ถ้าตรงกัน → คืนค่า i (index ของสมาชิกที่เจอ) และหยุดทันที
• ถ้าไม่ตรง → เลื่อน i ไปตำแหน่งถัดไป (i++) และกลับไปข้อ 2
• ถ้าตรวจครบทุกตำแหน่งแล้วยังไม่เจอ → คืนค่า -1

ฟังก์ชัน linearSearch(values, target):
  สำหรับ i จาก 0 ถึง values.length - 1:
    ถ้า values[i] เท่ากับ target:
      คืนค่า i
  คืนค่า -1

หัวใจมีแค่นี้: loop + if + return ถ้าเข้าใจ loop for และการเปรียบเทียบค่า คุณก็เขียน Linear Search ได้แล้ว

โค้ด JavaScript พร้อมคำอธิบาย

function linearSearch(values, target) {
  for (let i = 0; i < values.length; i += 1) {
    if (values[i] === target) {
      return i;
    }
  }
  return -1;
}

// ตัวอย่างการใช้งาน
const numbers = [4, 9, 2, 7, 5];

console.log(linearSearch(numbers, 7));  // 3  (พบ 7 ที่ index 3)
console.log(linearSearch(numbers, 4));  // 0  (พบที่ index แรก)
console.log(linearSearch(numbers, 8));  // -1 (ไม่มี 8 ในอาเรย์)
console.log(linearSearch([], 3));       // -1 (อาเรย์ว่าง ตรวจอะไรไม่ได้)

อธิบายทีละส่วน: • `for (let i = 0; i < values.length; i++)` — วน loop ตั้งแต่ index 0 จนถึงตัวสุดท้าย • `if (values[i] === target)` — เปรียบเทียบค่าที่ตำแหน่งปัจจุบันกับค่าเป้าหมาย • `return i` — เจอแล้วหยุดทันที คืน index ที่เจอ • `return -1` — หลุดจาก loop แสดงว่าตรวจครบแล้วไม่เจอ จึงคืน -1 Edge cases ที่โค้ดจัดการให้: • อาเรย์ว่าง (length = 0) → for loop ไม่รันเลย → return -1 • เจอที่ index แรก → return ทันที (Best Case O(1)) • target ปรากฏหลายครั้ง → คืน index แรกสุดที่เจอ

ทดลองเขียน Linear Search

วิเคราะห์ประสิทธิภาพ (Time & Space Complexity)

• Best Case: O(1) — เจอเป้าหมายที่ index แรกของอาเรย์
• Average Case: O(n/2) ≈ O(n) — โดยเฉลี่ยต้องตรวจประมาณครึ่งหนึ่งของข้อมูล
• Worst Case: O(n) — ไม่เจอเลย (ต้องตรวจทุกตัว) หรือเจอที่ตำแหน่งสุดท้าย

พื้นที่หน่วยความจำ (Space Complexity) = O(1) — ฟังก์ชันแบบ iterative ใช้ตัวแปรเพิ่มแค่ `i` เท่านั้น ไม่ต้องสร้างโครงสร้างข้อมูลใหม่

ข้อดี ข้อเสีย และกรณีใช้งาน

เปรียบเทียบกับ Binary Search

กฎสำคัญที่ต้องจำ

ทบทวนความเข้าใจ

แบบฝึกหัด: ฝึกเขียน Linear Search

แบบฝึกหัด 3 ข้อนี้จะช่วยให้คุณเขียน Linear Search ได้คล่อง — เริ่มจากการคืน index แบบพื้นฐาน ไปจนถึงการคืนทุกตำแหน่งที่พบ