Cài đặt tìm kiếm nhị phân
Trong video này, bạn đã học cách cài đặt tìm kiếm tuyến tính và tìm kiếm nhị phân và thấy sự khác nhau giữa chúng.
Trong bài tập này, bạn cần cài đặt hàm binary_search(). Bạn làm được chứ?
Bài tập này là một phần của khóa học
Cấu trúc dữ liệu và Thuật toán với Python
Hướng dẫn bài tập
- Kiểm tra xem giá trị cần tìm có bằng giá trị ở giữa hay không.
- Kiểm tra xem giá trị cần tìm có nhỏ hơn giá trị ở giữa hay không.
- Gán
lastbằng giá trịmiddletrừ một.
Bài tập tương tác thực hành trực tiếp
Hãy thử làm bài tập này bằng cách hoàn thành đoạn mã mẫu này.
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))