Binary Search Algorithm คือ อะไร ใช้ทำอะไร
ถ้าเรามีข้อมูลมากมายเก็บอยุ่ใน data set การจะค้นหาข้อมูลจะทำได้ 2 แบบคือ Sequential search และ Binary search ซึ่งวันนี้เราจะมาคุยกันนะคับว่าแบบหลังมีดีกว่ายังไง
รูปด้านล่างเป็นการเปรียบเทียบ Binary search (Linear search) and Sequential search ซึ่งจะพบว่าในการค้นหา “37” จาก data set ชุดนี้ Binary search จะใช้เพียงแค่ 3 steps เท่านั้น ในขณะที่ Sequential search จะต้องไล่เช็คแบบ linear ถึง 11 steps (ช้ากว่ามาก) แต่ถ้าข้อมูลที่จะค้นหาอยุ่อันดับต้นๆ แบบ Binary search อาจทำได้เร็วกว่านะ
ในการค้นหาแบบ Binary search ข้อมูลจะถูกดำเนินการดังนี้
- จัดเรียงข้อมูลทั้งหมดใน data set (sorting) ก่อน
- ตรวจสอบข้อมูลที่เราต้องการตรวจสอบ (target) ว่าอยุ่ส่วนไหน
- วิธีการตรวจสอบจะทำการแบ่งทีละครึ่งของข้อมูลด้วย // (หารไม่เอาเศษ) และเช็คว่าน้อยกว่าหรือมากกว่าค่า target ของเรา
- ถ้าน้อยกว่า ก็ให้แบ่งอีกครึ่งถัดไป, ถ้ามากกว่า ก็ให้ถอยหลังกลับมาแบ่งครึ่งก่อนหน้า
ถ้า Targer < data[mid] ให้เลื่อน high มาเป็น mid-1
ถ้า Target > data [mid] ให้เลื่อน low มาเป็น mid+1
เพื่อเป็นการกำหนด range ให้จำกัดวงของ target มากขึ้น
มาดูตัวอย่างจาก Code Python กันเลยนะครับ
data = [1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59]def binary_search(data, target, low, high):
if low > high:
return False
else:
mid = (low + high)//2
if target == data[mid]:
return True
elif target < data[mid]:
return binary_search(data, target, low, mid - 1)
else:
return binary_search(data, target, mid + 1, high)target = int(input("Input your number do you want to find: "))
print(binary_search(data, target, 0, len(data)-1))
if target in data:
print("{} is in data set".format(target))
else:
print("{} NOT in data set".format(target))
เมื่อรันแล้วจะได้ ผลลัพธ์ตามนี้
ชั้นตอนการคิดจาก Page Ar.Nest นะครับ อธิบายได้ชัดเจนมากๆ
แล้วพบกันใหม่ครับ
