logo

Viết chương trình của thuật toán tìm kiếm nhị phân với dãy sắp xếp giảm dần

Cùng Toploigiai Trả lời câu hỏi trang 93 (Viết chương trình của thuật toán tìm kiếm nhị phân với dãy sắp xếp giảm dần) Bài 19: Bài toán tìm kiếm SGK Tin 11 Kết nối tri thức.

Câu hỏi: Viết chương trình của thuật toán tìm kiếm nhị phân với dãy sắp xếp giảm dần

thuật toán tìm kiếm nhị phân

Trả lời ngắn gọn: 

Dưới đây là chương trình của thuật toán tìm kiếm nhị phân với dãy sắp xếp giảm dần:

def binary_search(arr, x):
   low = 0
   high = len(arr) - 1
   while low <= high:
       mid = (low + high) // 2
       if arr[mid] == x:
           return mid
       elif arr[mid] > x:
           low = mid + 1
       else:
           high = mid - 1
   return -1

Chương trình trả về chỉ số của phần tử cần tìm trong mảng nếu tìm thấy, nếu không tìm thấy thì trả về -1.

Trả lời chi tiết:

Để thực hiện thuật toán tìm kiếm nhị phân trên một dãy sắp xếp giảm dần trong Python ta có thể sử dụng vòng lặp while để tiến hành tìm kiếm. Dưới đây là một chương trình mẫu của thuật toán tìm kiếm nhị phân trên một dãy sắp xếp giảm dần bằng Python:

def binary_search(arr, x):
   left = 0
   right = len(arr) - 1

   while left <= right:
       mid = (left + right) // 2

       if arr[mid] == x:
           return mid
       elif arr[mid] < x:
           right = mid - 1
       else:
           left = mid + 1

   return -1

# Sử dụng hàm để tìm kiếm giá trị 5 trong dãy sắp xếp giảm dần [9, 8, 6, 5, 3, 1]
arr = [9, 8, 6, 5, 3, 1]
x = 5
result = binary_search(arr, x)

if result != -1:
   print("Element is present at index", str(result))
else:
   print("Element is not present in array")

Trong chương trình này, ta truyền vào hàm binary_search một dãy sắp xếp giảm dần và một giá trị cần tìm kiếm. Ta khởi tạo hai biến left và right lần lượt bằng 0 và độ dài của mảng trừ đi 1. Sau đó, trong khi left nhỏ hơn hoặc bằng right, ta tính chỉ số giữa mid của dãy và kiểm tra nó có bằng giá trị cần tìm kiếm x không. Nếu có, ta trả về chỉ số mid. Nếu không, ta kiểm tra xem giá trị của mid có lớn hơn x hay không. Nếu lớn hơn, ta cập nhật lại right thành mid - 1, ngược lại ta cập nhật lại left thành mid + 1. Cuối cùng, nếu không tìm thấy giá trị x, ta trả về -1.

Ở ví dụ trên, ta sử dụng hàm binary_search để tìm kiếm giá trị 5 trong dãy sắp xếp giảm dần [9, 8, 6, 5, 3, 1]. Kết quả trả về là chỉ số 3, tương ứng với vị trí của giá trị 5 trong dãy.

>> Xem toàn bộ: Soạn Tin 11 Kết nối tri thức

icon-date
Xuất bản : 04/03/2023 - Cập nhật : 10/04/2023