Có tên nào cho loại tìm kiếm nhị phân này không?

Question

Bằng văn bản một số mã ngày hôm nay, tôi đã xảy ra khi một hoàn cảnh đã khiến tôi viết một tìm kiếm nhị phân của một loại mà tôi chưa bao giờ thấy trước đây. Liệu tìm kiếm nhị phân này có một tên, và nó thực sự là một tìm kiếm "nhị phân"?

Động lực

Trước hết, để làm cho việc tìm kiếm dễ dàng hơn để hiểu, tôi sẽ giải thích các trường hợp sử dụng mà sinh ra sự sáng tạo của mình.

Giả sử bạn có danh sách các số có thứ tự. Bạn được yêu cầu tìm chỉ mục của số trong danh sách gần nhất với x.

int findIndexClosestTo(int x); 

Các cuộc gọi đến findIndexClosestTo()luôn theo quy tắc này:

Nếu kết quả cuối cùng của findIndexClosestTo() là i, sau đó chỉ số gần gũi hơn với i đã xác xuất cao hơn là kết quả của cuộc gọi hiện tại để findIndexClosestTo().

Nói cách khác, chỉ mục chúng tôi cần tìm thời gian này có nhiều khả năng gần hơn với lần cuối chúng tôi tìm thấy gần hơn so với lần cuối chúng tôi tìm thấy.

Ví dụ: hãy tưởng tượng một cậu bé được mô phỏng đi bên trái và bên phải trên màn hình. Nếu chúng ta thường truy vấn chỉ mục vị trí của cậu bé, có khả năng anh ấy ở đâu đó gần nơi cuối cùng chúng tôi tìm thấy anh ấy.

Algorithm

Với trường hợp trên, chúng ta biết kết quả cuối cùng của findIndexClosestTo() là i (nếu điều này thực sự là lần đầu tiên các chức năng đã được gọi là, i mặc định là chỉ số giữa của danh sách, vì đơn giản, mặc dù một tìm kiếm nhị phân riêng biệt để tìm kết quả của cuộc gọi đầu tiên thực sự sẽ nhanh hơn), và hàm này đã được gọi lại. Căn cứ vào số điện thoại mới x, chúng tôi làm theo thuật toán này để tìm chỉ số của nó:

1. interval = 1;
2. Sản phẩm số chúng ta đang tìm kiếm, x, đặt ở i? Nếu có, hãy trả lại i;
3. Nếu không, hãy xác định xem x ở trên hoặc bên dưới i. (Hãy nhớ rằng, danh sách được sắp xếp.)
4. Di chuyển interval chỉ mục theo hướng x.
5. Nếu chúng tôi đã tìm thấy x tại vị trí mới của chúng tôi, hãy trả lại vị trí đó.
6. Double interval. (Ví dụ interval *= 2)
7. Nếu chúng ta đã trôi qua x, quay trở lại interval chỉ số, thiết lập interval = 1, đi đến 4.

Với quy tắc xác xuất đã nêu ở trên (dưới tiêu đề Động lực), điều này dường như tôi trở thành cách hiệu quả nhất để tìm chỉ mục chính xác. Bạn có biết cách nhanh hơn không?

Answer 1

gì bạn đang làm là (IMHO) một phiên bản của Interpolation search

Trong một tìm kiếm nội suy bạn giả định con số này được chia đều, và sau đó bạn cố gắng đoán vị trí của một số từ số đầu tiên và cuối cùng và độ dài của mảng.

Trong trường hợp của bạn, bạn đang sửa đổi phép nội suy sao cho bạn cho rằng Khóa rất gần với số cuối cùng bạn đã tìm kiếm.

Cũng lưu ý rằng bản ngã của bạn tương tự như bản ngã nơi TCP cố gắng tìm kích thước gói tối ưu. (Không nhớ tên :()

1. Bắt đầu chậm
   1. đúp khoảng
   2. nếu gói không khởi động lại từ thành công cuối cùng packet./ Khởi động lại từ kích thước gói tin mặc định .. 3.

Answer 2

Điều này đang diễn ra khỏi đầu của tôi, vì vậy tôi không có gì để sao lưu nó nhưng cảm giác ruột!

Tại bước 7, nếu chúng ta đã vượt qua x, nó có thể được nhanh hơn để giảm một nửa interval, và quay trở lại về phía x - hiệu quả, interval = -(interval/2), chứ không phải đặt lại interval để 1.

tôi sẽ phải phác họa ra một vài con số trên giấy, mặc dù ...

Chỉnh sửa: Xin lỗi - Tôi đang nói vô nghĩa ở trên: bỏ qua tôi! (Và tôi sẽ đi xa và có một thích suy nghĩ về nó thời gian này ...)

Answer 3

Trong trường hợp xấu nhất, thuật toán của bạn là O ((log n)^2).

Giả sử bạn bắt đầu từ 0 (với khoảng = 1), và giá trị mà bạn tìm kiếm thực sự nằm ở vị trí 2^n - 1.

Trước tiên, bạn sẽ kiểm tra 1, 2, 4, 8, ... , 2^(n-1), 2^n. Rất tiếc, điều đó vượt quá, vì vậy hãy quay lại 2^(n-1).

Tiếp theo bạn kiểm tra 2^(n-1) +1, 2^(n-1) +2, ..., 2^(n-1) + 2^(n-2), 2^(n-1) + 2^(n-1). Đó là thuật ngữ cuối cùng là 2^n, do đó, rất tiếc, điều đó sẽ lặp lại lần nữa. Quay lại 2^(n-1) + 2^(n-2).

Và như vậy, cho đến khi bạn cuối cùng đã đạt được 2^(n-1) + 2^(n-2) + ... + 1 == 2^n - 1.

Các vượt qua đầu tiên mất log n bước. Các bước tiếp theo (log n) -1 bước. Lần tiếp theo (log n) - 2 bước. Và cứ thế.

Vì vậy, trường hợp xấu nhất, bạn đã thực hiện các bước 1 + 2 + 3 + ... + log n == O ((log n)^2).

Ý tưởng hay hơn, tôi nghĩ, là chuyển sang tìm kiếm nhị phân truyền thống khi bạn vượt qua lần đầu tiên. Điều đó sẽ bảo vệ hiệu suất trường hợp xấu nhất O (log n) của thuật toán, trong khi có xu hướng nhanh hơn một chút khi đích thực sự ở gần.

Tôi không biết tên cho thuật toán này, nhưng tôi thích nó. (Bằng một sự trùng hợp kỳ lạ, tôi có thể đã sử dụng nó ngày hôm qua. Thật.)

Answer 4

Thường trình của bạn là điển hình của thói quen nội suy. Bạn không mất nhiều nếu bạn gọi nó với số ngẫu nhiên (~ tìm kiếm nhị phân chuẩn), nhưng nếu bạn gọi nó với số tăng dần, sẽ không mất nhiều thời gian để tìm chỉ mục chính xác.

Do đó, đây là hành vi mặc định hợp lý để tìm kiếm bảng được sắp xếp cho mục đích nội suy.

Phương pháp này được thảo luận với độ dài lớn trong phiên bản Công thức số 3, phần 3.1.