Tìm kiếm nhảy bước

Tìm kiếm nhảy bước giống cách bạn tìm một trang trong cuốn sách không có mục lục: lật tới từng xấp trang, liếc số trang, và khi đã lật quá, lần ngược lại trong xấp cuối. Trên danh sách đã sắp xếp, nó cần ít phép so sánh hơn nhiều so với kiểm tra từng giá trị.

Một hàng cột đã sắp xếp chia thành các khối, cột cuối của mỗi khối bị bỏ qua mờ đi và khối có thể chứa mục tiêu được tô bóng
Một hàng cột đã sắp xếp chia thành các khối, cột cuối của mỗi khối bị bỏ qua mờ đi và khối có thể chứa mục tiêu được tô bóng

Ý tưởng

Trong danh sách đã sắp xếp, giá trị cuối của một khối cho biết mục tiêu có thể nằm trong khối đó hay không: nếu nó nhỏ hơn mục tiêu, mọi giá trị trong khối cũng nhỏ hơn. Vì vậy không cần xem bên trong. Lần lượt kiểm tra giá trị cuối của từng khối, bỏ qua cả khối, cho đến khi gặp một giá trị không nhỏ hơn mục tiêu. Khi đó mục tiêu chỉ có thể nằm trong khối đó: quét khối từ đầu.

Ví dụ

Tìm 23 trong 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 với các khối 3 giá trị. Khối đầu kết thúc bằng 8, nhỏ hơn, nên bỏ qua. Khối thứ hai kết thúc bằng 23, không nhỏ hơn, nên 23 chỉ có thể nằm trong 12, 16, 23. Quét khối này được 12, 16 rồi 23: tìm thấy sau 5 phép so sánh, trong khi tìm kiếm tuyến tính cần 6 và tìm kiếm nhị phân cần 3. Khi tìm 40, các giá trị cuối khối 8, 23 và 72 dẫn đến khối 38, 56, 72; 38 nhỏ hơn và 56 đã lớn hơn, nên 40 không có ở đó: lại là 5 phép so sánh.

Vì sao là √n

Với các khối m giá trị, tìm đúng khối cần tối đa khoảng n/m phép so sánh và quét khối đó tối đa m. Nhảy ít mà xa thì quét lâu; nhảy nhiều mà ngắn thì nhảy lâu. Tổng n/m + m nhỏ nhất khi hai phần bằng nhau, tại m = √n, khi đó nó vào khoảng 2√n. Với 40 giá trị, nghĩa là các khối 6 giá trị và tối đa 13 phép so sánh; với một triệu giá trị, các khối 1.000 giá trị và khoảng 2.000 phép so sánh.

Khi nào nên dùng

Tìm kiếm nhị phân cần ít phép so sánh hơn, khoảng log₂ n. Nhưng tìm kiếm nhị phân nhảy tới nhảy lui khắp danh sách, còn tìm kiếm nhảy bước chỉ đi tới và lùi một lần, về đầu một khối. Điều đó khiến nó hấp dẫn với dữ liệu trên băng từ hoặc trong cấu trúc liên kết, nơi việc đi lùi chậm. Ben Shneiderman mô tả nó với tên jump searching vào năm 1978. Cùng ý tưởng chia thành √n khối, thường gọi là phân rã căn bậc hai, xuất hiện trong nhiều thuật toán khác.

Ben Shneiderman (trái) với Catherine Plaisant tại Webshop 2012. Shneiderman mô tả tìm kiếm nhảy năm 1978.
Ben Shneiderman (trái) với Catherine Plaisant tại Webshop 2012. Shneiderman mô tả tìm kiếm nhảy năm 1978.

Khám phá

Mở ứng dụng, chọn một giá trị ở Tìm, rồi nhấn Bước. Mỗi bước nhảy làm nổi bật giá trị cuối của một khối; các khối bị bỏ qua mờ đi, còn khối có thể chứa mục tiêu được tô bóng trong lúc quét. Đổi Bước nhảy từ √n sang 2 hoặc 8 với 40 cột và xem sự cân bằng giữa nhảy và quét thay đổi.

Câu hỏi thường gặp

Độ phức tạp thời gian của tìm kiếm nhảy bước là gì?

O(√n) với các khối √n giá trị: tối đa khoảng 2√n phép so sánh. Nó cần O(1) bộ nhớ thêm và một danh sách đã sắp xếp.

Tìm kiếm nhảy bước khác tìm kiếm nhị phân thế nào?

Tìm kiếm nhị phân chia đôi phần còn lại mỗi lần và cần khoảng log₂ n phép so sánh, nhưng di chuyển tới lui. Tìm kiếm nhảy bước nhảy tới theo bước cố định và quét một khối, cần khoảng 2√n phép so sánh, và chỉ lùi một lần.

Lần quét trong khối cuối có thể dùng tìm kiếm nhị phân không?

Có. Tìm trong khối bằng tìm kiếm nhị phân giảm lần quét từ m phép so sánh xuống khoảng log₂ m. Các bước nhảy vẫn tốn n/m, nên khi đó khối lớn hơn sẽ có lợi.

Tìm kiếm nhảy bước có cần danh sách đã sắp xếp không?

Có. Bỏ qua một khối chỉ an toàn vì giá trị cuối của nó nhỏ hơn nghĩa là mọi giá trị trong khối đều nhỏ hơn. Ứng dụng sắp xếp danh sách chưa sắp xếp trước.

Sẵn sàng thử chưa?

Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.

Thử tìm kiếm nhảy bước