Khi được yêu cầu thực hiện tìm kiếm nhị phân bằng cách sử dụng đệ quy, một phương pháp có thể được xác định, phương pháp này sẽ kiểm tra xem chỉ số 'cao' có lớn hơn chỉ số 'thấp hay không. Dựa trên giá trị có tại biến 'mid', hàm được gọi lại để tìm kiếm phần tử.
Một danh sách có thể được sử dụng để lưu trữ các giá trị không đồng nhất (tức là dữ liệu thuộc bất kỳ kiểu dữ liệu nào như số nguyên, dấu phẩy động, chuỗi, v.v.).
Dưới đây là một minh chứng cho điều tương tự -
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("The list is")
print(my_list)
my_result = binary_search(my_list,0,len(my_list)-1,elem_to_search)
if my_result != -1:
print("Element found at index ", str(my_result))
else:
print("Element not found!") Đầu ra
The list is [1, 9, 11, 21, 34, 54, 67, 90] Element found at index 0
Giải thích
- Một hàm có tên 'binary_search' được xác định.
- Nó lấy danh sách, biến "low", biến "high" và phần tử được tìm kiếm làm tham số.
- Sau đó, biến "mid" được gán giá trị trung bình của các biến "high" và "low".
- Nếu phần tử ở 'mid' giống với phần tử cần tìm kiếm, phần tử đó sẽ được trả về.
- Ngược lại, nếu phần tử ở vị trí 'giữa' lớn hơn phần tử được tìm kiếm, thì hàm sẽ được gọi lại bằng cách chuyển các tập tham số khác nhau.
- Nếu không, nếu phần tử ở vị trí 'giữa' nhỏ hơn phần tử cần tìm kiếm, hàm sẽ được gọi lại bằng cách chuyển một bộ tham số khác.
- Bây giờ danh sách đã được xác định và hàm được gọi bằng cách chuyển danh sách này dưới dạng tham số.
- Dữ liệu của thao tác này được lưu trữ trong một biến.
- Biến này là đầu ra được hiển thị trên bảng điều khiển.