การค้นหาเชิงเส้น (Linear Search) ด้วยภาษา Scala

 

เมื่อคุณพูดถึงการค้นหาข้อมูลในโปรแกรม การเลือกวิธีการค้นหาที่เหมาะสมเป็นสิ่งสำคัญอย่างยิ่ง ไม่ว่าจะเป็นการค้นหาข้อมูลในลิสต์ การค้นหาหมายเลขโทรศัพท์ หรือการค้นหาอีเมลในแคตาล็อก คำตอบที่ง่ายที่สุดที่เรามีอยู่คือ การค้นหาเชิงเส้น (Linear Search) ในบทความนี้ เราจะพูดถึง Linear Search ว่าคืออะไร พร้อมตัวอย่างโค้ดที่ทำงานในภาษา Scala รวมถึงการวิเคราะห์ความซับซ้อนและข้อดีข้อเสียของวิธีนี้

 

Linear Search คืออะไร?

Linear Search คือ Algorithm ที่ทำหน้าที่ค้นหาองค์ประกอบในลิสต์แบบเรียงลำดับ โดยเริ่มจากต้นลิสต์และทำการเปรียบเทียบทุกองค์ประกอบทีละตัวเพื่อหาค่าที่ต้องการ วิธีนี้อยู่บนพื้นฐานของหลักการที่ว่า ถ้าคุณต้องการหาสิ่งหนึ่งในชุดที่ไม่เรียงลำดับ คุณต้องมองไปที่ทุกๆ คนในกลุ่มนั้นจนกว่าจะเจอ หรือจนกว่าจะรู้ว่ามันไม่มีอยู่ในกลุ่ม

การทำงานของ Linear Search

1. เริ่มจากตำแหน่งแรกของลิสต์

2. เปรียบเทียบค่าในตำแหน่งปัจจุบันกับค่าที่ต้องการ

3. หากตรงกัน ให้คืนค่าตำแหน่งนั้น

4. หากไม่ตรง ให้ไปยังตำแหน่งถัดไป

5. ทำซ้ำจนกว่าจะเจอค่าที่ต้องการหรือจบลิสต์

 

ตัวอย่างโค้ดใน Scala

มาเจาะลึกกันที่ตัวอย่างโค้ดกันดีกว่า โดยในตัวอย่างนี้เราจะสร้างฟังก์ชันค้นหาเชิงเส้นในลิสต์ของจำนวนเต็ม:

 object LinearSearch {
  def linearSearch(array: Array[Int], target: Int): Int = {
    for (i <- array.indices) {
      if (array(i) == target) {
        return i // คืนค่าตำแหน่งที่พบ
      }
    }
    -1 // คืนค่า -1 หากไม่พบ
  }

  def main(args: Array[String]): Unit = {
    val numbers = Array(4, 2, 7, 1, 3)
    val target = 7
    val result = linearSearch(numbers, target)

    if (result != -1) {
      println(s"พบ $target ที่ตำแหน่ง $result")
    } else {
      println("ไม่พบค่าที่ต้องการ")
    }
  }
}

เมื่อรันโปรแกรมนี้ ระบบจะค้นหาค่าของ 7 ในอาร์เรย์ และแสดงผลออกมาว่าค่าดังกล่าวอยู่ที่ตำแหน่งไหน

 

Use Case ในโลกจริง

การค้นหาสินค้าในระบบ e-commerce:

ในกรณีนี้ Linear Search สามารถใช้เพื่อตรวจสอบว่ามีสินค้าใดๆ ในสต็อกหรือไม่ โดยอาจทำการค้นหาผลิตภัณฑ์จากรายการสินค้าที่ไม่ผ่านการจัดเรียง

การค้นหาหมายเลขโทรศัพท์:

เมื่อลูกค้าต้องการค้นหาหมายเลขโทรศัพท์ในรายชื่อ เมื่อการเรียงลำดับไม่ใช่ตัวเลือกที่นำมาพิจารณา Linear Search คือทางออกที่ง่ายและรวดเร็ว

 

การวิเคราะห์ Complexity

เวลาที่ใช้ (Time Complexity):

Linear Search มีความซับซ้อน O(n) ซึ่งหมายความว่าหากจำนวนข้อมูลเพิ่มขึ้น เวลาในการค้นหาก็จะเพิ่มตามไปด้วย เนื่องจากคุณต้องเปรียบเทียบกับทุกอนุกรมในลิสต์ ในกรณีที่เลวร้ายที่สุด คุณอาจต้องเปรียบเทียบถึง n ครั้ง

พื้นที่ใช้ (Space Complexity):

Linear Search ใช้พื้นที่ O(1) เพราะว่าไม่ต้องใช้หน่วยความจำเพิ่มเติมตามขนาดของข้อมูลที่ค้นหา

 

ข้อดีและข้อเสียของ Linear Search

ข้อดี:

- เรียบง่าย: โค้ดการค้นหานี้เข้าใจง่ายและเขียนได้อย่างรวดเร็ว - ไม่จำเป็นต้องจัดเรียงข้อมูล: สามารถค้นหาในข้อมูลที่ไม่เรียงลำดับและไม่ต้องการการเตรียมข้อมูลที่ซับซ้อน

ข้อเสีย:

- ค่อนข้างช้า: เมื่อข้อมูลมีขนาดใหญ่ การค้นหายังคงใช้เวลานาน (O(n)) ซึ่งอาจไม่เหมาะสมในการค้นหาในลิสต์ขนาดใหญ่ - ไม่เหมาะสมสำหรับการค้นหาบ่อย ๆ: ถ้าจำเป็นต้องค้นหาข้อมูลอยู่มากอาจต้องหาทางเลือกอื่น เช่น Binary Search หรือ Hashing

 

สรุป

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

หากคุณสนใจที่จะเรียนรู้ความรู้เกี่ยวกับ Programming อย่างจริงจังและต้องการเข้าใจ Concept ของ Algorithm ต่าง ๆ ในลักษณะที่ลึกซึ้งมากขึ้นอย่าลืมศึกษาที่โรงเรียน EPT (Expert-Programming-Tutor) ที่นี่เรามีหลักสูตรที่สามารถช่วยให้คุณกลายเป็นนักพัฒนาซอฟต์แวร์ที่เก่งขึ้นหลากหลายภาษา อาทิ Scala, Python, Java และอีกมากมาย!

เมื่อคุณมีความรู้เกี่ยวกับ Linear Search แล้ว ทำไมไม่ลองนำมันไปใช้ในโครงการของตัวเองดูล่ะ?

 

 

หมายเหตุ: ข้อมูลในบทความนี้อาจจะผิด โปรดตรวจสอบความถูกต้องของบทความอีกครั้งหนึ่ง บทความนี้ไม่สามารถนำไปใช้อ้างอิงใด ๆ ได้ ทาง EPT ไม่ขอยืนยันความถูกต้อง และไม่ขอรับผิดชอบต่อความเสียหายใดที่เกิดจากบทความชุดนี้ทั้งทางทรัพย์สิน ร่างกาย หรือจิตใจของผู้อ่านและผู้เกี่ยวข้อง