C++ 查找算法学习合集

悠悠 2023-02-10 07:54 198阅读 0赞

**1.顺序查找**  
全局遍历搜索匹配，暴力检索，不提倡。  
**2.二分查找**  
常见的二分查找就是二叉树的性质，每次都查找剩余的一半。所以它的事件复杂度也即是O（logN）。虽然二分查找算法的效率很高（这也是二分查找算法被广泛应用的原因），但是前提就是说查找的序列：**有序**。在需要频繁进行插入或者删除操作的数据记录中使用二分查找算法效率不是很高，因为还要维持数据的有序还需要额外的排序开销。  
**3.二分查找变种**  
**1.插值查找算法**  
变种的地方主要在于mid值的计算方法。在有序序列当中，当我们所要查找的value偏小或者偏大，如果再用二分就会造成开销的过大。所以插值查找算法当中mid值的计算方法就是将其更偏向查找值value，已达到更高的效率。  
二分查找中mid值计算：  
![在这里插入图片描述][20200520202723294.png]  
插值查找算法中mid值计算：  
![在这里插入图片描述][20200520202738716.png]

**2.斐波拉契数列查找**，根据黄金分割法来查找关键值，效率比二分法还是要高一些。在该算法中的mid值接为：  
![在这里插入图片描述][20200520202754236.png]

//顺序查找
    int SequenceSearch(string str, char value)
    {
        
    	for (int i = 0; i <= str.length(); i++)
    	{
        
    		if (str[i] == value)
    		{
        
    			return i;
    		}
    	}
    }
    //折半查找（二分查找）
    int BinarySearch(string str,char value)
    {
        
    	int low, high, mid;
    	low = 0;
    	high = str.length() - 1;
    	while (low <= high)
    	{
        
    		mid = (low + high) / 2;
    		if (str[mid] == value)
    			return mid;
    		if (str[mid] > value)//如果查找值在下半区，
    			high = mid - 1;
    		if (str[mid] < value)//如果查找值在上半区，
    			low = mid + 1;
    	}
    }
    //插值查找（基于二分查找）自适应二分查找
    int InsertionSearch(string str, char value)
    {
        
    	int low, high, mid;
    	low = 0;
    	high = str.length()-1;
    	while (low <= high)
    	{
        
    		mid = low + (value -str[low])/(str[high]-str[low])*(high - low);//自适应的中值寻找,让中值跟家靠近顺序表中查找值的位置，相比二分更有效率
    		if (str[mid] == value)
    			return mid;
    		if (str[mid] > value)
    			high = mid - 1;
    		if (str[mid] < value)
    			low = mid + 1;
    	}
    
    }// 也可用递归
    
    //斐波那契查找 
    void Fibonacci(int * F)
    {
        
    	F[0] = 0; F[1] = 1;
    	for (int i = 2; i < 20; ++i)
    		F[i] = F[i - 1] + F[i - 2];
    }/*定义斐波那契数列*/
    const int max_size = 20;//斐波那契数组的长度 /*构造一个斐波那契数组*/
    
    int FibonacciSearch(int *arr, int key, int length)//a为要查找的数组,n为要查找的数组长度,key为要查找的关键字 
    {
        
    	int low = 0; int high = length - 1;
    	int F[max_size];
    	Fibonacci(F);//构造一个斐波那契数组F 
    	int k = 0;
    	while (length > F[k])//计算n位于斐波那契数列的位置 
    	{
        
    		k++;
    	}
    	int * temp;//将数组a扩展到F[k]-1的长度
    	temp = new int[F[k] - 1];
    	memcpy(temp, arr, length * sizeof(int));
    
    	for (int i = length; i < F[k] - 1; i++)
    	{
        
    		temp[i] = arr[length - 1];
    	}
    
    	while (low <= high)
    	{
        
    		int mid = low + F[k - 1] - 1;
    		if (key == temp[mid]) return mid;
    		if (key < temp[mid])
    		{
        
    			high = mid - 1;
    			k -= 1;
    		}
    		else if (key > temp[mid])
    		{
        
    			low = mid + 1;
    			k -= 2;
    		}	
    	}
    	delete temp;
    	return -1;
    }
    
    int main()
    {
        
    	//	string str = "326584910710";
    	//	 sort(str.begin(),str.end());
    	//	cout<< BinarySearch(str, '9');
    
    	int a[] = {
         16,22,15,41,45,52,88,99，100,150,500 };
    	int length = sizeof(a) / sizeof(int);
    	int key = 500;
    	int index = FibonacciSearch(a, key, length);
    	cout << key << " is located at : " << index;
    	return 0;
    }

[20200520202723294.png]: https://img-blog.csdnimg.cn/20200520202723294.png
[20200520202738716.png]: https://img-blog.csdnimg.cn/20200520202738716.png
[20200520202754236.png]: https://img-blog.csdnimg.cn/20200520202754236.png