Linear Search อัลกอริทึม

Linear Search Algorithm คืออะไร แนวคิดเป็นยังไง บทความนี้มีคำตอบครับ พร้อมโค้ดตัวอย่างด้วยภาษา Python

Linear Search คืออะไร ?

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

โดย Linear Search เป็น searching algorithm อีกรูปแบบหนึ่งที่เราคงได้ยินบ่อย ๆ เฉกเช่นเดียวกันกับ Binary Search ที่หลาย ๆ คนที่เรียนสาย Computer Science หรือ Engineering คงคุ้นเคยกันดี โดย Linear Search นั้น เรียกได้ว่าเป็น Searching Algorithm ที่เรียบง่ายที่สุด เพราะอะไร? มาดูกันครับ

ลำดับการทำงานของ Linear Search

ลำดับการทำงานอัลกอริทึมของ Linear Search จะมีสเต็ปดังต่อไปนี้ครับ

1. กำหนดค่าที่ต้องการเสิร์ช (Target Value)
2. ทำการเสิร์ชหรือเทียบค่าไปทีละตัว ตั้งแต่ index ตัวที่ 1 (ลำดับที่ 0) ไปเรื่อย ๆ จนกว่าจะเจอ Target Value หรือไปจนถึงตัวสุดท้าย (ในกรณี worst case)
   
3. ถ้าเจอ Target Value ก็รีเทิร์น index ของค่านั้นออกมา จบการทำงาน
   
4. ถ้าค่านั้นไม่มีใน List หรือ Array ก็รีเทิร์น None จบการทำงาน
   

numbers = [8, 5, 9, 1, 13, 15, 2, 7]

จากค่าข้อมูลใน List (Python)

Best Case: 8 --> โชคดีหน่อยเมื่อค้นหา 8

Worst Case: 7 --> โชคร้ายสุดเมื่อค้นหา 7

เห็นไหมครับว่า Linear Search จะค้นหาไปแบบลำดับ ถ้าค่าที่เราค้นหาอยู่ใน index ต้น ๆ แล้วก็จะค้นหาได้ไวอยู่  แต่ถ้าอยู่ท้าย ๆ ก็จะยิ่งช้าลงไปตามขนาดของ List หรือ Array  โดยประสิทธิภาพเมื่อเทียบกับเวลา (Time Complexity) ของ Linear Search นั้นจะเป็น O(n) ซึ่ง n ก็คือจำนวนข้อมูลนั่นเอง

โค้ดตัวอย่าง Linear Search

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  
    return None  

numbers = [8, 5, 9, 1, 13, 15, 2, 7]
target_number = 13

result = linear_search(numbers, target_number)
if result is not None:
    print(f"Target number {target_number} found at index {result}.")
else:
    print("Target number not found.")

# Output
Target number 13 found at index 4.

1. สร้างฟังก์ชันที่ชื่อ   linear_search()   โดยกำหนดค่าพารามิเตอร์ 2 ตัวคือ   arr   และ   target   เพื่อรับค่าข้อมูลที่อยู่ใน Array (หรือ List) ตามด้วยค่าที่ต้องการค้นหา ตามลำดับ 
2.  Loop ค่าจำนวน index ทั้งหมดที่อยู่ใน List ออกมาโดยใช้ for loop โดยกำหนดจำนวนใน arr ด้วยฟังก์ชัน  len()  (เพื่อแปลงเป็นจำนวน members ทั้งหมดที่อยู่ใน arr)
3. สร้างเงื่อนไขเพื่อเปรียบเทียบค่าที่ลูปออกมา  arr[i]   กับค่า Target ที่เราต้องการค้นหา ถ้าตรงกันกับ Target ให้รีเทิร์น  i   ซึ่งเป็น index ของค่าที่เรากำลังค้นหา ถ้าไม่เจอให้รีเทิร์น None เป็นอันเสร็จสิ้นฟังก์ชันการเสิร์ช
   
4. กำหนดตัวแปร  numbers   เพื่อสร้างข้อมูลแบบ List เป็นข้อมูลที่เราจะใช้ทดสอบค้นหา รวมทั้งกำหนดค่าที่เราต้องการค้นหา คือ 13 โดยแทนด้วยตัวแปร  target_number 
5. กำหนดตัวแปร  result   เพื่อใช้แสดงผลลัพธ์ค่าที่เราเสิร์ช จากนั้น assign ฟังก์ชัน linear_search(numbers, target_number)   ที่ได้สร้างไว้ในตอนแรกเข้ามาพร้อมกับอากิวเมนต์ 2 ตัว คือ numbers และ target_number ซึ่งเป็นข้อมูลใน List และ ค่าที่ต้องการค้นหา ตามลำดับ
6. จากนั้นกำหนดเงื่อนไข if-else เพื่อแสดงผลลัพธ์ในรูปแบบที่ต้องการได้เลย
   
   

สรุป

• เทียบค่าหรือเสิร์ชค่าไปทีละตัวตั้งแต่ index ตัวแรกจนถึง index ตัวสุดท้าย
• ข้อมูลใน Array หรือ List ที่ค้นหา ไม่จำเป็นต้องเป็นข้อมูลที่เรียงลำดับหรือไม่เรียงลำดับ (Sorted Numbers or Unsorted Numbers) ก็คือจะ sort หรือไม่ sort ก็ได้
• ประสิทธิภาพเมื่อเทียบกับเวลา (Time Complexity) คือ O(n)
• เป็นเสิร์ชอัลกอริทึมที่เรียบง่ายที่สุด