Chương trình Python triển khai Tìm kiếm nhị phân (Binary Search) không dùng đệ quy

Khi cần triển khai tìm kiếm nhị phân không dùng đệ quy, định nghĩa phương thức kiểm tra chỉ số đầu và cuối của list, lấy giá trị giữa.

So sánh với giá trị cần tìm. Nếu tìm thấy, trả về giá trị. Ngược lại trả về -1.

Lưu ý: Tìm kiếm nhị phân chỉ hoạt động trên dữ liệu đã sắp xếp (tăng hoặc giảm).

List lưu trữ giá trị đa dạng.

Minh họa:

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("Danh sách là:")
print(my_list)
my_result = binary_search(my_list, 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 phương thức 'binary_search' nhận list và phần tử cần tìm.
• Gán low=0, mid=0.
• Gán high = len(list)-1.
• Chia lấy nguyên để lấy 'mid' chỉ khi low <= high.
• Tìm từ low đến mid nếu giá trị < mid.
• Tìm từ mid đến high nếu giá trị > mid và < high.
• Định nghĩa list.
• Gọi phương thức với list.
• Kết quả lưu trong biến.
• Hiển thị biến đầu ra.