[C++] Các thuật toán tìm kiếm cơ bản thường sử dụng

Thuật toán tìm kiếm nội suy (interpolation search) (code này chỉ áp dụng cho mảng đã sắp xếp tăng dần)

Mã: Chọn tất cả

#include <iostream>


using namespace std;


int InterpolationSearch(int A[], int n, int x)
{
    int left = 0;
    int right = n - 1;
    int mid;
    while (left <= right && x >= A[left] && x <= A[right])
    {
        mid = left + (right - left) * (x - A[left]) / (A[right] - A[left]);
        if (A[mid] == x)
            return mid;
        if (A[mid] > x)
            right = mid - 1;
        else if (A[mid] < x)
            left = mid + 1;
    }
    return -1; // Không tìm thấy x
}

int main()
{

    int arr[] {-33,-26,-5,1,2,3,7,12,32,45,53,71,80,99,100};

    int n = sizeof(arr) / sizeof(arr[0]); // so luong phan tu trong mang

    cout << "So luong phan tu trong mang: " << n << endl;

    cout << InterpolationSearch(arr, n, -5);

    return 0;
}