Tìm kiếm nhảy (Jump Search) - Thuật toán cho mảng đã sắp xếp

Jump Search dùng cho danh sách có thứ tự. Tạo khối (block) kích thước √n, kiểm tra phần tử cuối khối. Nếu khóa lớn hơn, nhảy sang khối tiếp. Tìm thấy khối chứa khóa, dùng linear search trong khối. Hiệu năng giữa linear và binary search.

Độ phức tạp

• Thời gian: O(√n)
• Không gian: O(1)

Đầu vào / Đầu ra

Input:  Sorted: 10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995, key=356
Output: Item found at location: 11

Thuật toán

jumpSearch(array, size, key)
Begin
    blockSize := √size
    start := 0, end := blockSize
    while array[end] <= key AND end < size:
        start := end
        end := end + blockSize
        if end > size-1: end := size
    done
    for i = start to end-1:
        if array[i] == key: return i
    done
    return invalid location
End

Ví dụ C++

#include <iostream>
#include <cmath>
using namespace std;

int jumpSearch(int arr[], int n, int key) {
    int start = 0, end = sqrt(n);
    while(arr[end] <= key && end < n) {
        start = end;
        end += sqrt(n);
        if(end > n-1) end = n;
    }
    for(int i=start; i> n;
    int arr[n]; cout << "Enter items: " << endl;
    for(int i=0;i> arr[i];
    cout << "Enter search key: "; cin >> key;
    if((loc=jumpSearch(arr,n,key))>=0) cout << "Item found at location: " << loc << endl;
    else cout << "Item not found." << endl;
}

Kết quả

Enter number of items: 20
Enter items: 10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995
Enter search key: 356
Item found at location: 11