Khi bắt buộc phải triển khai tìm kiếm nhị phân mà không sử dụng từ điển, một phương pháp có thể được xác định để kiểm tra chỉ mục đầu tiên và chỉ mục cuối cùng của danh sách và lấy giá trị giữa của danh sách.
Sau đó, nó được so sánh với giá trị cần được kiểm tra. Nếu nó được tìm thấy, giá trị được trả về. Ngược lại, -1 được trả về.
Điều quan trọng cần nhớ là tìm kiếm nhị phân chỉ hoạt động trên các phần tử được sắp xếp, theo thứ tự tăng dần hoặc giảm dần.
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, 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!") Đầu ra
The list is [1, 9, 11, 21, 34, 54, 67, 90] Element found at index 0
Giải thích
- Một phương thức có tên 'binary_search' được xác định để lấy danh sách và phần tử cần tìm làm tham số.
- Một biến thấp được gán cho 0 và biến giữa được gán cho 0.
- Giá trị cao của biến được chỉ định bằng độ dài của danh sách-1.
- Phép chia tầng theo từng bit được thực hiện để lấy giá trị cho biến "giữa", chỉ khi giá trị "thấp" nhỏ hơn hoặc bằng "cao"
- Đầu tiên, phần tử được tìm kiếm từ chỉ mục thấp đến giữa, nếu giá trị nhỏ hơn giá trị có ở chỉ mục giữa.
- Khác, phần tử được tìm kiếm từ chỉ mục trung bình đến cao, nếu giá trị lớn hơn trung bình và nhỏ hơn cao.
- Bây giờ, một danh sách đã được xác định.
- Phương thức được gọi bằng cách chuyển danh sách trên 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.