การ implement Binary Search
ในวิดีโอที่ผ่านมา คุณได้เรียนรู้วิธี implement linear search และ binary search รวมถึงเห็นความแตกต่างระหว่างทั้งสองแล้ว
ในแบบฝึกหัดนี้ ให้ implement ฟังก์ชัน binary_search() ลองทำดูกัน!
แบบฝึกหัดนี้เป็นส่วนหนึ่งของหลักสูตร
โครงสร้างข้อมูลและอัลกอริทึมใน Python
คำแนะนำการฝึกหัด
- ตรวจสอบว่าค่าที่ต้องการค้นหาเท่ากับค่าที่อยู่ตรงกลางหรือไม่
- ตรวจสอบว่าค่าที่ต้องการค้นหาน้อยกว่าค่าที่อยู่ตรงกลางหรือไม่
- กำหนดให้
lastเท่ากับค่าของmiddleลบหนึ่ง
แบบฝึกหัดเชิงโต้ตอบแบบลงมือทำ
ลองทำแบบฝึกหัดนี้โดยเติมโค้ดตัวอย่างนี้ให้สมบูรณ์
def binary_search(ordered_list, search_value):
first = 0
last = len(ordered_list) - 1
while first <= last:
middle = (first + last)//2
# Check whether the search value equals the value in the middle
if ____ == ____:
return True
# Check whether the search value is smaller than the value in the middle
elif ____ < ____:
# Set last to the value of middle minus one
____
else:
first = middle + 1
return False
print(binary_search([1,5,8,9,15,20,70,72], 5))