Tôi tình cờ đang xây dựng tìm kiếm nhị phân trong Python, nhưng câu hỏi có nhiều hơn để làm với cấu trúc tìm kiếm nhị phân nói chung. Giả sử tôi có khoảng một ngàn ứng cử viên đủ điều kiện tôi đang tìm kiếm thông qua tìm kiếm nhị phân, thực hiện cách tiếp cận cổ điển để chia nhỏ tập dữ liệu được sắp xếp và lặp lại quy trình này để thu hẹp tập hợp đủ điều kiện để lặp lại. Các thí sinh chỉ là chuỗi tên, (định dạng đầu cuối, ví dụ: "Peter Jackson") Tôi ban đầu sắp xếp các thiết lập thứ tự abc và sau đó tiến hành chia làm hai đoạn sử dụng một cái gì đó như thế này:Tìm kiếm chuỗi nhị phân - chiều rộng thùng tối thiểu?
hi = len(names)
lo = 0
while lo < hi:
mid = (lo+hi)//2
midval = names[mid].lower()
if midval < query.lower():
lo = mid+1
elif midval > query.lower():
hi=mid
else:
return midval
return None
Mã này chuyển thể từ đây: https://stackoverflow.com/a/212413/215608
Đây là điều, quy trình trên giả định một kết quả khớp chính xác hoặc không có kết quả nào cả. Điều gì sẽ xảy ra nếu truy vấn chỉ đơn thuần là một "Peter", nhưng có một số peters có tên họ khác nhau? Để trả lại tất cả các Peters, người ta sẽ phải đảm bảo rằng "bins" chia đôi không bao giờ có quá nhỏ như ngoại trừ kết quả đủ điều kiện. Quá trình bisection sẽ phải chấm dứt và nhượng lại một cái gì đó giống như một regex/thường xuyên chuỗi trận đấu cũ để trả lại tất cả các Peters.
Tôi không yêu cầu cách thực hiện điều này là loại tìm kiếm này được gọi là ... tìm kiếm nhị phân với tiêu chí phân tách cho "kích thước bin" được gọi là gì? Một cái gì đó có điều kiện chia nhỏ tập dữ liệu và khi tiêu chí được hoàn thành, hãy quay lại một số dạng kết hợp chuỗi khác để đảm bảo rằng có thể có ký tự kết thúc có hiệu quả trên truy vấn (do đó tìm kiếm "Peter" sẽ nhận được " Peter Jacksons "và" Peter Edwards ")
Hy vọng rằng tôi đã rõ ràng ý tôi là gì. Tôi nhận ra trong kịch bản DB điển hình các tên có thể được tách ra, đây chỉ là dự định như là một bằng chứng về khái niệm.
trong trường hợp xấu nhất có thể là tất cả các peters, phải không? – kdubs
Thật vậy, trong kịch bản tồi tệ nhất (hoặc tôi nên nói một dự định?) Tất cả các Peters sẽ được lấy. – DeaconDesperado
vì vậy có vẻ như bạn muốn bạn phải bin theo những gì bạn có thể tìm kiếm theo. Tôi đoán bạn có thể làm một nhị phân cho đến khi bạn tìm thấy một trận đấu, và sau đó thực hiện tìm kiếm tuyến tính theo cả hai hướng để tìm tất cả các trận đấu khác. không chắc chắn nếu tôi muốn gọi nó là thùng, nhưng bạn sẽ có dữ liệu của bạn được tổ chức thành một cây nhị phân và tuyến tính. – kdubs