Viết hàm thực hiện tìm kiếm nhị phân nhận hai tham số đầu vào

Viết hàm thực hiện tìm kiếm nhị phân nhận hai tham số đầu vào: dãy số a và giá trị x cần tìm.

Giải Tin học 11 Bài 7: Lập trình giải bài toán tìm kiếm - Cánh diều

Nhiệm vụ 3 trang 120 Tin học 11: Viết hàm thực hiện tìm kiếm nhị phân nhận hai tham số đầu vào: dãy số a và giá trị x cần tìm.

Lời giải:

#Trả về chỉ số của x trong arr nếu tồn tại, nếu không có sẽ trả về -1

def binary_search(arr, low, high, x):

#Trường hợp cơ sở

if high >= low:

mid = (high + low) // 2

#Nếu phần tử có tồn tại ở phần giữa của mảng

if arr[mid] == x:

return mid

#Nếu phần tử nhỏ hơn mid, nó sẽ nằm ở phía bên trái của mảng điểm gốc là tử phần tử mid

elif arr[mid] > x:

return binary_search(arr, low, mid - 1, x)

#Nếu không, phần tử sẽ nằm bên phải

else:

return binary_search(arr, mid + 1, high, x)

else:

#Phần tử không tồn tại trong tập hợp

return -1

#Khởi tạo tập hợp

arr = [ 2, 3, 4, 10, 40 ]

x = 10

#Gọi hàm

result = binary_search(arr, 0, len(arr)-1, x)

if result != -1:

print("Phần tử cần tìm có chỉ số là ", str(result))

else:

print("Phần tử cần tìm không có trong mảng.")

Lời giải Tin 11 Bài 7: Lập trình giải bài toán tìm kiếm hay khác: