Câu hỏi:
11/06/2023 136Viế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.
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:
#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.")
Quảng cáo
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
a. Viết chương trình phython thực hiện tìm kiếm tuần tự
b. Viết phiên bản tìm kiếm tuần tự thứ hai, dùng vòng lặp for thay cho vòng lặp while (hoặc ngược lại).
c. Viết phiên bản tìm kiếm tuần tự có thêm hai tham số đầu vào lo và hi tương tự như của hàm index. So sánh kết quả với phương thức index của phython.
Câu 3:
Em hãy tính số phép toán sơ cấp, điền vào cột bên phải của bảng ở Hình 2 ước lượng độ phức tạp thời gian của thuật toán tìm kiếm tuần tự.
Câu 4:
Theo em, với dãy đã sắp thứ tự và cho một số x cụ thể
a) Trường hợp nào tìm kiếm tuần tự nhanh hơn tìm kiếm nhị phân?
b) Về trung bình thuật toán tìm kiếm tuần tự hay thuật toán tìm kiếm nhị phân tốt hơn?
Câu 5:
Em hãy thực hiện các yêu cầu sau:
1. Viết mã giả cho thuật toán tìm kiếm nhị phân.
2. Ước lượng số lần thực hiện vòng lặp trong thuật toán tìm kiếm nhị phân.
3. Ước lượng độ phức tạp thời gian của thuật toán tìm kiếm nhị phân.
Câu 6:
Viết chương trình tìm kiếm vị trí tên của một người trong mỗi danh sách sau đây:
a. Danh sách học sinh của lớp em.
b. Danh sách tên của các chủ tài khoản ngân hàng (kí tự không dấu) và đã sắp thứ tự theo bảng chữ cái.
Câu 7:
Khi tạo mới một tài khoản người dùng, em được yêu cầu nhập tên người dùng “user name”. Có trường hợp em phải nhập lại tên khác vì tên vừa nhập đã có người sử dụng rồi. Theo em, máy tính làm gì ngay sau khi nhận được yêu cầu tạo mới một tài khoản? Hãy phát biểu thành một bài toán.
về câu hỏi!