เมื่อต้องการทำ Binary Search โดยไม่ใช้ Recursion สามารถกำหนดเมธอดที่ตรวจสอบดัชนีแรกและสุดท้ายของลิสต์ และหาค่ากลางของลิสต์
เปรียบเทียบกับค่าที่ต้องการตรวจสอบ หากพบ ให้คืนค่า มิฉะนั้นคืนค่า -1
สำคัญ: Binary Search ทำงานกับข้อมูลที่เรียงลำดับแล้วเท่านั้น ไม่ว่าจะเป็น昇序 หรือ 降序
ลิสต์สามารถเก็บค่าที่หลากหลายได้
ตัวอย่าง
def binary_search(my_list, elem):
low = 0
high = len(my_list) - 1
mid = 0
while low <= high:
mid = (high + low) // 2
if my_list[mid] < elem:
low = mid + 1
elif my_list[mid] > elem:
high = mid - 1
else:
return mid
return -1
my_list = [1, 9, 11, 21, 34, 54, 67, 90]
elem_to_search = 1
print("The list is")
print(my_list)
my_result = binary_search(my_list, elem_to_search)
if my_result != -1:
print("Element found at index ", str(my_result))
else:
print("Element not found!")
ผลลัพธ์
The list is [1, 9, 11, 21, 34, 54, 67, 90] Element found at index 0
คำอธิบาย
- กำหนดเมธอด 'binary_search' รับลิสต์และองค์ประกอบที่ต้องการค้นหาเป็นพารามิเตอร์
- กำหนดตัวแปร low = 0 และ mid = 0
- ตัวแปร high กำหนดเป็นความยาวลิสต์ - 1
- ทำ floor division เพื่อหาค่า 'mid' กรณี 'low' น้อยกว่าหรือเท่ากับ 'high'
- ค้นหาองค์ประกอบจาก low ถึง mid หากค่าน้อยกว่าค่าที่ mid
- มิฉะนั้น ค้นหาจาก mid ถึง high หากค่ามากกว่า mid และน้อยกว่า high
- กำหนดลิสต์
- เรียกเมธอดโดยส่งลิสต์ข้างต้นเป็นพารามิเตอร์
- ข้อมูลจากการดำเนินการนี้ถูกเก็บในตัวแปร
- ตัวแปรนี้คือเอาต์พุทที่แสดงบนคอนโซล
