เขียนโปรแกรม จาก กิจกรรมที่ 2.10 ค้นข้อมูล ด้วยภาษา Python ซึ่งเป็นวิธีการค้นหาแบบทวิภาค หรือ เรียกอีกอย่างหนึ่งว่า Binary Tree

โจทย์

พิจารณารายการข้อมูลต่อไปนี้ ทำการค้นหาตัวเลข 62 แล้วคืนค่าตำแหน่งของข้อมูล

8, 9, 13, 35, 42, 44, 50, 54, 58, 60, 61, 62, 77, 84, 86, 90, 92, 96

เริ่มเขียนโปรแกรมกันเถอะ !

---

l = [8, 9, 13, 35, 42, 44, 50, 54, 58, 60, 61, 62, 77, 84, 86, 90, 92, 96]
#สร้างรายการข้อมูล l
target = 8
#กำหนด target
n = len(l)
#กำหนด n ให้เท่ากับจำนวนข้อมูลในรายการ l 
#โดยใช้ฟังก์ชัน len() หาจำนวนข้อมูลทั้งหมด
left = 0
#กำหนด left เริ่มต้น = 0 เนื่องจากข้อมูลในคอมพิวเตอร์ 
#จะเริ่มที่ตำแหน่งที่ 0 ไม่ใช่ 1
right = n-1
#กำหนด right เริ่มต้น = n-1 
#ที่ต้อง n-1 เนื่องจากข้อมูลในคอมพิวเตอร์ จะเริ่มที่ตำแหน่งที่ 0 
#สมมุติว่า ข้อมูลอยู่ตำแหน่งที่ 9 หากนับตำแหน่ง
#ในรูปแบบคอมพิวเตอร์ก็จะอยู่ในตำแหน่งที่ 8
i = None
#กำหนดค่า i ให้เท่ากับค่าว่าง 
while left<=right:
  #กำหนดเงื่อนไขการทำงานของลูปเป็น left<=right
  mid = int((left+right)/2)
  #หาตำแหน่งกึ่งกลางของข้อมูลโดย (left+right)/2 
  #พร้อมทั้งบังคับให้เป็นจำนวนเต็มโดยใช้คำสั่ง int()
  x = l[mid]
  #ให้ x เท่ากับข้อมูลในตำแหน่งที่ mid
  print(left,right,mid,x)
  if x<target:
    left = mid+1
    #ถ้า x น้อยกว่าค่าที่ต้องการหา ให้ขยับ left เป็น mid+1
  elif x>target:
    right = mid-1
    #ถ้า x มากกว่าค่าที่ต้องการหา ให้ขยับ right เป็น mid-1
  else :
    i = mid
    break
    #นอกเหนือจาก 2 เงื่อนไขด้านบน จะเหลือแค่กรณีที่ x = target 
    #ให้ i = mid แล้วหยุดการทำงาน
if i!=None:
  print(target,"อยู่ตำแหน่งที่",i+1)
  #หาก i มีค่า ให้แสดงผลตำแหน่งของ Target
else :
  print("ไม่พบ",target)
  #หาก i ไม่มีค่า แสดงว่าไม่พบ Target

---

ศึกษาขั้นตอนวิธีแบบละเอียดได้ที่ กิจกรรมที่ 2.10 ค้นข้อมูล