Thuật toán tìm kiếm nhị phân Python
Tìm kiếm danh sách được sắp xếp theo thời gian logarit O(log n). Chạy và hiểu tìm kiếm nhị phân trong Python, bao gồm logic từng bước, các trường hợp phức tạp và tối ưu hóa.
Tổng quan
Tìm kiếm nhị phân là một thuật toán đặc biệt hiệu quả để tìm một mục trong danh sách được sắp xếp. Không giống như tìm kiếm tuyến tính quét mọi phần tử một cách tuần tự trong thời gian O(n), tìm kiếm nhị phân hoạt động bằng cách liên tục chia đôi khoảng thời gian tìm kiếm.
Việc tìm kiếm bắt đầu bằng việc kiểm tra phần tử ở giữa của mảng. Nếu giá trị đích khớp với phần tử ở giữa thì vị trí của nó sẽ được trả về. Nếu mục tiêu nhỏ hơn, thuật toán sẽ thu hẹp tìm kiếm của nó xuống nửa dưới; nếu mục tiêu lớn hơn, nó sẽ thu hẹp mục tiêu xuống nửa trên. Quá trình này lặp lại cho đến khi tìm thấy phần tử hoặc kích thước mảng con giảm xuống 0.
Để triển khai tìm kiếm nhị phân trong Python, chúng tôi sử dụng hai con trỏ (thấp và cao) để theo dõi ranh giới tìm kiếm đang hoạt động. Do không gian tìm kiếm giảm một nửa ở mỗi bước nên thuật toán thực thi trong thời gian O(log n), lý tưởng cho các cơ sở dữ liệu lớn.
Đầu ra mã & thực thi
Triển khai tìm kiếm nhị phân lặp tiêu chuẩn trả về chỉ mục của phần tử đích trong danh sách được sắp xếp.
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
guess = arr[mid]
if guess == target:
return mid
if guess > target:
high = mid - 1
else:
low = mid + 1
return -1
# Sorted test dataset
data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target_val = 23
index = binary_search(data, target_val)
print(f"Dataset: {data}")
print(f"Target: {target_val}")
if index != -1:
print(f"Target found at index: {index}")
else:
print("Target not found in dataset")Dataset: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
Target: 23
Target found at index: 5Triển khai từng bước
- Lập chỉ mục truy vấn và tìm kiếm trong các bảng cơ sở dữ liệu
- Tìm giá trị ngưỡng hoặc giá trị biên trong phạm vi toán học liên tục
- Chức năng tự động hoàn thành và tìm kiếm trong trường văn bản
Câu hỏi thường gặp
Danh sách có phải được sắp xếp để tìm kiếm nhị phân hoạt động không?
Có, tìm kiếm nhị phân hoàn toàn dựa vào các phần tử được sắp xếp. Nếu danh sách không được sắp xếp, logic so sánh sẽ bị hỏng và bạn phải sắp xếp danh sách trước hoặc sử dụng tìm kiếm tuyến tính.
Tại sao nên sử dụng tìm kiếm nhị phân lặp trên tìm kiếm nhị phân đệ quy?
Mặc dù tìm kiếm nhị phân đệ quy rất hay nhưng tìm kiếm nhị phân lặp lại thường được ưu tiên hơn trong sản xuất. Cách tiếp cận lặp lại chạy trong không gian phụ trợ O(1), trong khi tìm kiếm đệ quy chiếm không gian O(log n) do ngăn xếp cuộc gọi, có nguy cơ tràn ngăn xếp trên các đầu vào cực lớn.
Chủ đề liên quan
Khám phá các thuật toán sắp xếp python. Trực quan hóa sắp xếp bong bóng và sắp xếp hợp nhất nguyên bản trong ngữ cảnh IDE của trình duyệt.
Hướng dẫn thuật toán sắp xếp hợp nhất PythonTìm hiểu cách triển khai Sắp xếp hợp nhất trong Python. Ví dụ tương tác từng bước về chiến lược sắp xếp Phân chia và Chinh phục.
Hướng dẫn thuật toán Quicksort của PythonKhám phá thuật toán quicksort trong Python. Tìm hiểu lựa chọn trục, phân vùng và đệ quy trong ví dụ mã hóa tương tác này.