顺序查找

教程

顺序查找是最简单的查找算法，从数据结构的起始位置开始，逐个比较每个元素，直到找到目标元素或者遍历完所有元素

特点

适用于无序和有序列表
时间复杂度：O(n)

空间复杂度：O(1)

代码实现

//顺序查找函数（基本查找）
int sequentialSearch(int arr[],int size, int target) {
	for (int i = 0;i < size;i++) {
		if (arr[i] == target) {
			return i;//返回目标元素的下标
		}
	}
	return -1;//未找到目标元素，返回-1
}

二分查找

教程

二分查找针对已经排序的数组，通过不断将搜索区间对半分割来快速定位目标元素

工作原理

确定数组的中间元素
如果中间元素等于目标值，查找成功
如果目标值小于中间元素，在左半部分继续查找
如果目标值大于中间元素，在右半部分继续查找
特点

仅适用于有序数组
时间复杂度：O(log n)

空间复杂度：O(1)

代码实现

#include<iostream>
using namespace std;
//二分查找函数
int binarySearch(int arr[], int size, int target) {
	int left = 0;
	int right = size - 1;
	while (left <= right) {
		int mid = left + (right - left) / 2;//防止溢出
		if (arr[mid] == target) {
			return mid;
		}
		else if (arr[mid] < target) {
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
	}
	return -1;
}

插值查找

教程

插值查找是二分查找的改进版本，使用于数据分布均匀的有序数组。它通过计算目标值在数组中的可能位置来进行查找。

公式

$pos=min+\frac{key-arr[min]}{arr[max]-arr[min]}*(max-min)$

特点

适用于分布均匀的有序数组
平均时间复杂度：O(log log n)
最坏情况时间复杂度：O(n)
代码实现

#include<iostream>
using namespace std;
插值查找函数
int interpolationSearch(int arr[], int size, int target) {
	int low = 0;
	int high = size - 1;
	while (low <= high && target >= arr[low] && target <= arr[high]) {
		//计算插值位置
		int pos = low + ((target - arr[low]) / (arr[high] - arr[low])) * (high - low);
		if (arr[pos] == target) {
			return pos; //找到目标值，返回索引
		}
		else if (arr[pos] < target) {
			low = pos + 1; //目标值在右侧
		}
		else {
			high = pos - 1; //目标值在左侧
		}
		return -1;//未找到目标值
	}

斐波那契查找

教程

斐波那契查找利用斐波那契数列来分割搜索区间，是二分查找的另一种变体

步骤

找到大于等于数组长度的最小斐波那契数
使用斐波那契数来分割数组
比较并决定在哪个子区间继续查找
特点

只涉及加减运算，适合大数据量

时间复杂度：O(log n)

代码实现

#include<iostream>
using namespace std;
//生成斐波那契数列数组
void generateFibonacci(int fib[], int& fibSize, int n){
	fib[0] = 0;
	fib[1] = 1;
	fibSize = 2;//初始大小为2
	while (fib[fibSize - 1] < n) {//生成斐波那契数列直到大于等于n
		fib[fibSize] = fib[fibSize - 1] + fib[fibSize - 2];//下一个斐波那契数
		fibSize++;//增加大小
	}
}
//斐波那契查找函数
int fibonacciSearch(int arr[], int size, int target) {
	int fib[20];
	int fibSize;
	generateFibonacci(fib, fibSize, size);
	
	int offset = -1;//偏移量
	int k = fibSize - 1;//斐波那契数列的下标
	while (k > 1) {
		int i = min(offset + fib[k - 2], size - 1);
		if (arr[i] < target) {//目标元素在右侧
			k = k - 1;//移动到下一个斐波那契数
			offset = i;
		}
		else if (arr[i] > target) {//目标元素在左侧
			k = k - 2;//移动到上上个斐波那契数
		} else {
			return i;
		}
	}
	if (k == 1 && arr[offset + 1] == target) {
		return offset + 1;
	}
	return -1;
}

分块查找

教程

分块查找将数据分成若干块，块内元素可以无序，但块间有序。建立索引表记录每块的最大关键字和起始位置。

步骤

将数组分成若干块
确定目标值可能所在的块
在该块内进行顺序查找
特点

适用于动态数据

时间复杂度O($\sqrt{n}$ )

代码实现

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

// 块结构体
struct Block {
    int max;        // 块内最大值
    int start;      // 块起始索引
    int end;        // 块结束索引
};
// 分块查找函数
int blockSearch(int arr[], int size, int target, int blockSize) {
    // 计算块数
    int blockCount = ceil(static_cast<double>(size) / blockSize);
    Block* blocks = new Block[blockCount];
    // 初始化块信息
    for (int i = 0; i < blockCount; i++) {
        blocks[i].start = i * blockSize;
        blocks[i].end = min((i + 1) * blockSize - 1, size - 1);
        blocks[i].max = arr[blocks[i].start];
        
        // 找到块内最大值
        for (int j = blocks[i].start; j <= blocks[i].end; j++) {
            if (arr[j] > blocks[i].max) {
                blocks[i].max = arr[j];
            }
        }
    }
    // 确定目标所在的块
    int targetBlock = -1;
    for (int i = 0; i < blockCount; i++) {
        if (target <= blocks[i].max) {
            targetBlock = i;
            break;
        }
    }
    if (targetBlock == -1) {
        delete[] blocks;
        return -1;
    }
    // 在目标块内顺序查找
    for (int i = blocks[targetBlock].start; i <= blocks[targetBlock].end; i++) {
        if (arr[i] == target) {
            delete[] blocks;
            return i;
        }
    }
    delete[] blocks;
    return -1;
}

哈希查找

原理

哈希查找通过哈希函数将关键字映射到哈希表中的位置，实现快速查找

关键概念

哈希函数：将关键字映射到哈希表位置
冲突解决：处理不同关键字映射到同一位置的情况
特点
平均时间复杂度：O(1)

需要额外的储存空间

代码实现

#include <iostream>
using namespace std;

// 哈希表大小
const int TABLE_SIZE = 10;

// 哈希节点结构
struct HashNode {
    int key;
    int value;
    HashNode* next;
    HashNode(int k, int v) : key(k), value(v), next(nullptr) {}
};
// 简单的哈希表类
class HashTable {
private:
    HashNode** table; // 指针数组
public:
    HashTable() {
        table = new HashNode*[TABLE_SIZE](); // 初始化为nullptr
    }
    ~HashTable() {
        for (int i = 0; i < TABLE_SIZE; i++) {
            HashNode* current = table[i];
            while (current != nullptr) {
                HashNode* temp = current;
                current = current->next;
                delete temp;
            }
        }
        delete[] table;
    }
    // 哈希函数
    int hashFunction(int key) {
        return key % TABLE_SIZE;
    }
    // 插入键值对
    void insert(int key, int value) {
        int index = hashFunction(key);
        HashNode* newNode = new HashNode(key, value);
        // 插入到链表头部
        newNode->next = table[index];
        table[index] = newNode;
    }
    // 查找键
    int search(int key) {
        int index = hashFunction(key);
        HashNode* current = table[index];
        while (current != nullptr) {
            if (current->key == key) {
                return current->value; // 返回对应的值
            }
            current = current->next;
        }
        return -1; // 未找到
    }
};