Skip to main content

linear-search-and-binary-search

การทำความเข้าใจเกี่ยวกับ Linear Search และ Binary Search เป็นการเรียนรู้เทคนิคพื้นฐานในการค้นหาข้อมูลในลิสต์หรืออาร์เรย์ที่ใช้ในโปรแกรมมิ่ง ซึ่งทั้งสองมีวิธีการและประสิทธิภาพที่แตกต่างกัน

1. Linear Search (การค้นหาลินีแร)​

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

  1. เริ่มจากตำแหน่งแรกของลิสต์
  2. ตรวจสอบแต่ละองค์ประกอบในลิสต์ว่าตรงกับค่าที่ต้องการหรือไม่
  3. หากพบข้อมูลที่ต้องการ ให้หยุดการค้นหา
  4. หากไม่พบข้อมูลที่ต้องการ และถึงจุดสิ้นสุดของลิสต์ ให้แสดงผลว่าไม่พบข้อมูล

ตัวอย่างโค้ด Linear Search (Python):​

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # คืนค่าดัชนีของข้อมูลที่พบ
    return -1  # หากไม่พบข้อมูล

# การทดสอบ Linear Search
arr = [10, 20, 30, 40, 50]
target = 30
result = linear_search(arr, target)

if result != -1:
    print(f"ข้อมูลที่ต้องการพบที่ดัชนี: {result}")
else:
    print("ไม่พบข้อมูลที่ต้องการ")

ผลลัพธ์:

ข้อมูลที่ต้องการพบที่ดัชนี: 2
  • ไม่จำเป็นต้องมีลิสต์ที่เรียงลำดับ: สามารถใช้ได้กับลิสต์ที่ไม่เรียงลำดับ
  • เข้าใจง่าย: เป็นวิธีที่ตรงไปตรงมาง่ายต่อการเขียนและเข้าใจ
  • ประสิทธิภาพต่ำ: หากลิสต์มีขนาดใหญ่ การค้นหาจะใช้เวลา O(n) โดยที่ n คือจำนวนขององค์ประกอบในลิสต์ ซึ่งหมายความว่าใช้เวลานานขึ้นเมื่อข้อมูลมากขึ้น

2. Binary Search (การค้นหาทวิภาค)​

Binary Search เป็นวิธีการค้นหาข้อมูลในลิสต์ที่เรียงลำดับแล้ว โดยการแบ่งลิสต์ออกเป็นสองส่วนและเลือกครึ่งหนึ่งที่คาดว่าจะมีข้อมูลที่ต้องการ แล้วทำการค้นหาซ้ำในครึ่งนั้นๆ

  1. ตรวจสอบค่าตรงกลางของลิสต์
  2. หากค่าตรงกลางตรงกับข้อมูลที่ต้องการ การค้นหาจะเสร็จสิ้น
  3. หากข้อมูลที่ต้องการมีค่าน้อยกว่าค่าตรงกลาง ให้ค้นหาในครึ่งซ้าย
  4. หากข้อมูลที่ต้องการมีค่ามากกว่าค่าตรงกลาง ให้ค้นหาในครึ่งขวา
  5. ทำซ้ำขั้นตอน 1-4 จนกว่าจะพบข้อมูลหรือหมดลิสต์

ตัวอย่างโค้ด Binary Search (Python):​

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    
    while low <= high:
        mid = (low + high) // 2  # คำนวณตำแหน่งกลาง
        if arr[mid] == target:
            return mid  # พบข้อมูลที่ต้องการ
        elif arr[mid] < target:
            low = mid + 1  # ค้นหาครึ่งขวา
        else:
            high = mid - 1  # ค้นหาครึ่งซ้าย
    
    return -1  # หากไม่พบข้อมูล

# การทดสอบ Binary Search
arr = [10, 20, 30, 40, 50]
target = 30
result = binary_search(arr, target)

if result != -1:
    print(f"ข้อมูลที่ต้องการพบที่ดัชนี: {result}")
else:
    print("ไม่พบข้อมูลที่ต้องการ")

ผลลัพธ์:

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

สรุป​

  • Linear Search: เป็นการค้นหาที่ง่ายและใช้ได้กับข้อมูลที่ไม่เรียงลำดับ แต่มีประสิทธิภาพต่ำเมื่อข้อมูลมากขึ้น
  • Binary Search: เป็นการค้นหาที่เร็วและมีประสิทธิภาพดีกว่าเมื่อข้อมูลเรียงลำดับแล้ว เพราะมีความซับซ้อน O(log n)

การเลือกวิธีการค้นหาควรพิจารณาจากลักษณะของข้อมูลและข้อกำหนดในงานที่ทำ