Khi cần triển khai tìm kiếm nhị phân dùng đệ quy, định nghĩa phương thức kiểm tra chỉ số 'high' có lớn hơn 'low'. Dựa trên giá trị tại biến 'mid', gọi lại hàm để tìm phần tử.
List lưu trữ giá trị đa dạng.
Minh họa:
Ví dụ
def binary_search(my_list, low, high, elem):
if high >= low:
mid = (high + low) // 2
if my_list[mid] == elem:
return mid
elif my_list[mid] > elem:
return binary_search(my_list, low, mid - 1, elem)
else:
return binary_search(my_list, mid + 1, high, elem)
else:
return -1
my_list = [1, 9, 11, 21, 34, 54, 67, 90]
elem_to_search = 1
print("Danh sách là:")
print(my_list)
my_result = binary_search(my_list, 0, len(my_list) - 1, elem_to_search)
if my_result != -1:
print("Phần tử tìm thấy tại index:", str(my_result))
else:
print("Không tìm thấy phần tử!")
Đầu ra
Danh sách là: [1, 9, 11, 21, 34, 54, 67, 90] Phần tử tìm thấy tại index: 0
Giải thích
- Định nghĩa hàm 'binary_search'.
- Nhận list, biến 'low', 'high' và phần tử cần tìm.
- Gán 'mid' = trung bình của 'high' và 'low'.
- Nếu phần tử tại 'mid' trùng với phần tử cần tìm, trả về.
- Ngược lại, nếu phần tử tại 'mid' lớn hơn, gọi lại hàm với tham số khác.
- Ngược lại, nếu phần tử tại 'mid' nhỏ hơn, gọi lại hàm với tham số khác.
- Định nghĩa list, gọi hàm với list làm tham số.
- Kết quả lưu trong biến.
- Hiển thị biến đầu ra.