Câu hỏi:
20/04/2023 178Viế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.
Siêu phẩm 30 đề thi thử THPT quốc gia 2024 do thầy cô VietJack biên soạn, chỉ từ 100k trên Shopee Mall.
Quảng cáo
Trả lời:
def binary_search_reverse(arr, target):
def binary_search_reverse_helper(arr, target, low, high):
if low > high:
return -1
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search_reverse_helper(arr, target, low, mid - 1)
else:
return binary_search_reverse_helper(arr, target, mid + 1, high)
return binary_search_reverse_helper(arr, target, 0, len(arr) - 1)
# Sử dụng ví dụ đầu vào để kiểm tra
arr = [10, 8, 6, 4, 2]
target = 6
# Gọi hàm tìm kiếm nhị phân với dãy sắp xếp giảm dần
result = binary_search_reverse(arr, target)
if result != -1:
print("Phần tử", target, "được tìm thấy tại vị trí", result)
else:
print("Phần tử", target, "không tồn tại trong dãy.")
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Cho dãy A = [1, 91, 45, 23, 67, 9, 10, 47, 90, 46, 86]. Thuật toán tìm kiếm tuần tự cần thực hiện bao nhiêu lần duyệt để tìm ra phần tử có giá trị bằng 47 trong dãy?
Câu 2:
Cho dãy A= {0, 4, 9, 10, 12,14, 17, 18, 20, 31, 34, 67}
Với thuật toán tìm kiếm tuần tự, cần duyệt bao nhiêu phần tử để tìm ra phần từ có giá trị bằng 34?
Câu 3:
Khi nào thì tìm kiếm tuần tự sẽ cần nhiều bước nhất? Cho ví dụ.
Câu 4:
Với thuật toán tìm kiếm nhị phân, cần duyệt bao nhiêu phần tử để tìm ra phân tử có giá trị bằng 34?
Câu 5:
Thay vị lần lượt lật các thẻ từ đầu đến cuối, bạn Minh đã chơi như sau: Đầu Tiên Minh lật thẻ ở giữa, sau đó tuỳ theo số ghi trên thẻ là lớn hơn hay nhỏ hơn số K mà lạt tiếp thẻ ở ngay bên trái hoặc ngay bên phải thẻ ở giữa. Trong trường hợp này, số lần nhiều nhất mà Minh phải lật để tìm ra thẻ in số K là bao nhiêu?
Câu 6:
Cho A là danh sách tên các học sinh trong lớp được sắp xếp theo thứ tự bảng chữ cái, viết thương trình tìm kiếm nhị phân để tìm ra các học sinh có tên là Minh.
Câu 7:
Em hãy chỉnh sửa thuật toán tìm tuần tự để tìm ra tất cả các phần tử trong dãy bằng giá trị cần tìm, biết dãy đó có nhiều phân tử bằng giá trị cần tìm.
về câu hỏi!