Theo em trước khi thực hiện thuận toán tìm kiếm nhị phân, đánh sách khách hàng cần thoả mãn điều kiện gì ?
Nếu không thỏa mãn điều kiện đó , thuận toán tìm kiếm nhị phân có thực hiện được không
K
Khách
Hãy nhập câu hỏi của bạn vào đây, nếu là tài khoản VIP, bạn sẽ được ưu tiên trả lời.
Những câu hỏi liên quan
QT
Quoc Tran Anh Le
Giáo viên
9 tháng 11 2023
Sau lần chia đôi đầu tiên, pham vi tìm kiếm còn lại n/2 số, sau khi chia đôi lần thứ hai, dãy còn lại n/4 số, sau khi chia đôi lần thứ dãy còn lại n/8, …sau khi chia đôi lần k dãy còn lại n/2.mũ k. Kết thúc khi 2 mũ k sấp xỉ n.
QT
Quoc Tran Anh Le
Giáo viên
9 tháng 11 2023
a. Ví dụ một bài toán tìm kiếm trong thực tế: Giáo viên muốn tìm tên bạn Chung trong danh sách lớp sau:
Các bước thực hiện thuật toán tìm kiếm nhị phân cho bài toán trên:
- Bước 1: Xét vị trí ở giữa dãy, đó là vị trí số 5
- Vì sau bước 2 đã tìm thấy tên học sinh nên thuật toán kết thúc.
b) Thuật toán tìm kiếm nhị phân
- Thuật toán tìm kiếm nhị phân thu hẹp được phạm vi tìm kiếm chỉ còn tối đa là một nửa sau mỗi lần lặp. Thuật toán chia bài toán thành những bài toán nhỏ hơn giúp tăng hiệu quả tìm kiếm.
Thuật toán tuần tự
- Mô tả thuật toán phải cụ thể, rõ ràng, đầy đủ, đầu vào là gì, đầu ra là gì và chỉ rõ sự kết thúc thuật toán.
- Cần mô tả thuật toán cho tốt thì người máy hay máy tính mới hiểu đúng và thực hiện được.
- Nếu không, kết quả thực hiện thuật toán có thể không như mong đợi.
TL
19 tháng 8 2023
Tham khảo:
#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.")
=> Trước khi thực hiện thuật toán tìm kiếm nhị phân, danh sách khách hàng cần phải được sắp xếp theo một thứ tự nhất định, thường là theo thứ tự tăng dần hoặc giảm dần.
--> Điều này là bắt buộc vì thuật toán tìm kiếm nhị phân hoạt động dựa trên việc so sánh giá trị cần tìm với giá trị ở vị trí giữa của danh sách, sau đó loại bỏ nửa danh sách không chứa giá trị cần tìm.
=> Nếu danh sách khách hàng không được sắp xếp, thuật toán tìm kiếm nhị phân sẽ không hoạt động chính xác.
--> Trong trường hợp này, có thể cần sử dụng một thuật toán tìm kiếm khác như tìm kiếm tuần tự, hoặc cần phải sắp xếp danh sách trước khi thực hiện tìm kiếm nhị phân.