Các Giải Thuật Tìm Kiếm - Searching Algorithms

Tìm kiếm cơ bản và nâng cao với các giải thuật, được hiện thực bằng ngôn ngữ C++.

Tìm kiếm tuần tự vét cạn - Sequential search

Giải thuật tìm kiếm cơ bản nhất, tìm từ đầu cho đến cuối.

123456789101112131415161718192021222324252627#include <iostream>
using namespace std;

#define N 100000

int numberOfElements, key;
int arr[N];

int sequentialSearch(int arr[], int numberOfElements, int key) {
    int index = 0;
    while(index < numberOfElements) {
        if (arr[index] == key)
            return index;
        index++;
    }
}

int main() {
    cin >> numberOfElements;
    for (int index = 0; index < numberOfElements; index++)
        cin >> arr[index];
    
    cin >> key;

    cout << linearSentinelSearch(arr, numberOfElements, key);
    return 0;
}

Sắp xếp nhanh - Quick sort

Hàm hỗ trợ sắp xếp (khi cần) cho các giải thuật tìm kiếm.

1234567891011121314151617181920void quickSort(int arr[], int left, int right) {
    if (left >= right) return;

    int L = left, R = right;

    int x = arr[(L + R) / 2];

    while (L < R) {
        while (arr[L] < x) L++;
        while (arr[R] > x) R--;

        if (L <= R) {
            swap(arr[L], arr[R]);
            L++;
            R--;
        }
    }
    quickSort(arr, left, R);
    quickSort(arr, L, right);
}

Tìm kiếm nhị phân - Binary search

Tìm kiếm nhị phân chỉ có ý nghĩa khi dữ liệu đã được sắp xếp, do đó ta hiện thực thêm hàm quickSort để sắp xếp dữ liệu trước.

123456789101112131415161718192021222324252627282930313233343536373839#include <iostream>
using namespace std;

#define N 100000

int numberOfElements, key;
int arr[N];

int binarySearch(int arr[], int numberOfElements, int key) {
    int left = 0, right = numberOfElements - 1;

    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == key) return mid;
        if (arr[mid] > key) 
            right = mid - 1;
        else 
            left = mid + 1;
    }

    return -1;
}

int main() {
    cin >> numberOfElements;
    for (int index = 0; index < numberOfElements; index++)
        cin >> arr[index];
    
    cin >> key;

    quickSort(arr, 0, numberOfElements - 1);

    for (int index = 0; index < numberOfElements; index++)
        cout <<  arr[index] << " ";

    cout << endl << binarySearch(arr, numberOfElements, key);
    
    return 0;
}

Tìm kiếm tuần tự lính canh - Linear sentinel search

12345678910111213141516171819202122232425262728#include <iostream>
using namespace std;

#define N 100000

int numberOfElements, key;
int arr[N];

int linearSentinelSearch(int arr[], int numberOfElements, int key) {
    arr[numberOfElements] = key;
    int index = 0;
    while(true) {
        if (arr[index] == key)
            return index;
        index++;
    }
}

int main() {
    cin >> numberOfElements;
    for (int index = 0; index < numberOfElements; index++)
        cin >> arr[index];
    
    cin >> key;

    cout << linearSentinelSearch(arr, numberOfElements, key);
    return 0;
}

Tìm kiếm nội suy - Interpolation search

Cần sắp xếp dữ liệu trước khi tìm kiếm hoặc dữ liệu đã được sắp xếp sẵn.

123456789101112131415161718192021222324252627282930313233343536373839#include <iostream>
using namespace std;

#define N 100000

int numberOfElements, key;
int arr[N];

int interpolationSearch(int arr[], int numberOfElements, int key) {
    int left = 0, right = numberOfElements - 1;

    while (left != right && arr[left] != arr[right]) {
        int mid = left + ((right - left) / (arr[right] - arr[left])) * (key - arr[left]);
        if (arr[mid] == key) return mid;
        if (arr[mid] > key) 
            right = mid - 1;
        else 
            left = mid + 1;
    }

    return -1;
}

int main() {
    cin >> numberOfElements;
    for (int index = 0; index < numberOfElements; index++)
        cin >> arr[index];

    cin >> key;

    quicksort(arr, 0, numberOfElements - 1);

    for (int index = 0; index < numberOfElements; index++)
        cout <<  arr[index] << " ";
    
    cout << endl << interpolationSearch(arr, numberOfElements, key);
    
    return 0;
}