C++基础查询算法实现

1. 二分查找

二分查找是一种效率较高的查找方法，其时间复杂度为 O(log n)。要求查找的数组必须是有序的。

int binarySearch(vector<int> &nums, int target)
{
    int left = 0;
    int right = nums.size() - 1;
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target)
        {
            return mid;
        }
        else if (nums[mid] < target)
        {
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }
    return -1; // 未找到目标值
}

2. 顺序查找

顺序查找是一种简单的查找方法，其时间复杂度为 O(n)。适用于无序数组。

int sequentialSearch(vector<int> &nums, int target)
{
    for (int i = 0; i < nums.size(); i++)
    {
        if (nums[i] == target)
        {
            return i;
        }
    }
    return -1; // 未找到目标值
}

3. 插值查找

插值查找是二分查找的改进版本，适用于分布均匀的有序数组。

int interpolationSearch(vector<int> &nums, int target)
{
    int left = 0;
    int right = nums.size() - 1;
    while (left <= right && target >= nums[left] && target <= nums[right])
    {
        int pos = left + ((target - nums[left]) * (right - left)) / (nums[right] - nums[left]);
        if (nums[pos] == target)
        {
            return pos;
        }
        else if (nums[pos] < target)
        {
            left = pos + 1;
        }
        else
        {
            right = pos - 1;
        }
    }
    return -1; // 未找到目标值
}

4. 哈希查找

哈希查找是一种高效的查找方法，其时间复杂度为 O(1)。适用于无序数组。

int hashSearch(vector<int> &nums, int target)
{
    unordered_map<int, int> hashMap;
    for (int i = 0; i < nums.size(); i++)
    {
        hashMap[nums[i]] = i;
    }
    return hashMap[target];
}