专栏首页AngelNI查找(上)

查找(上)

查找(静态查找)

1.顺序查找

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
	int a[101] ={5,16,20,27,30,36,44,55,60,67,74};
	vector<int > b(a,a+11);
	cout<<"5,16,20,27,30,36,44,55,60,67,74" <<endl;
	cout<<"请输入要查找的数字"<<endl;
	int k;
	cin>>k;
	for(int i =0;i<=b.size();++i)
	{
		if(b[i]==k)
			cout<<"位于第"<<i+1<<"个"<<endl;
	}
	return 0;
}

2.哨兵查找

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
	int a[20];
	cout<<"请输入序列长度"<<endl;
	int l ;
	cin>>l; 
	cout<<"请输入查找的序列"<<endl;
	for(int i=1;i<=l;++i)
		cin>>a[i];
	cout<<"请输入要查找的数字"<<endl;
	int k;
	cin>>k;
	a[0]=k;//定义哨兵
	int j;
	for( j =l;a[j]!=k;--j);
	cout<<"位于第"<<j<<"个"<<endl;
	return 0;
}

3.二分查找

#include<iostream>
#include<algorithm>
using namespace std;
int a[20];
int len ;
int k ;
int search_bin()
{
	int l=1,r = len;
	while(l<=r)
	{
		int mid = (l+r)/2;
		if(a[mid]==k)	return mid;
		else if(k<a[mid]) r = mid-1;
		else l = mid+1;
	}
}
int main()
{
	
	cout<<"请输入序列长度"<<endl;
	cin>>len; 
	cout<<"请输入查找的序列"<<endl;
	for(int i=1;i<=len;++i)
		cin>>a[i];
	cout<<"请输入要查找的数字"<<endl;
	cin>>k;
	//二分对有序序列查找 ,先排序,在查找
	sort(a,a+len);
	int ans = search_bin();
	cout<<"位于第"<<ans<<endl; 
	return 0;
}

4. 斐波那契查找

#include<iostream>
#include<algorithm>
using namespace std;
int a[100];
int F[100]; 
int len ;
int k ;
int Fibonacci_Search(int *a,int n,int key)
{
	int low,high,mid,i,k=0;
	low=1;	/* 定义最低下标为记录首位 */
	high=n;	/* 定义最高下标为记录末位 */
	while(n>F[k]-1)
		k++;
	for (i=n;i<F[k]-1;i++)
		a[i]=a[n];
	while(low<=high)
	{
		mid=low+F[k-1]-1;
		if (key<a[mid])
		{
			high=mid-1;		
			k=k-1;
		}
		else if (key>a[mid])
		{
			low=mid+1;		
			k=k-2;
		}
		else
		{
			if (mid<=n)
				return mid;		/* 若相等则说明mid即为查找到的位置 */
			else 
				return n;
		}	
	}
	return 0;
}
 
int main()
{
	F[0]=0;
	F[1]=1;
	for(int i = 2;i < 100;i++)  
	{ 
		F[i] = F[i-1] + F[i-2];  
	} 
	cout<<"请输入序列长度"<<endl;
	cin>>len; 
	cout<<"请输入查找的序列"<<endl;
	for(int i=1;i<=len;++i)
		cin>>a[i];
	cout<<"请输入要查找的数字"<<endl;
	cin>>k;
	
	int result=Fibonacci_Search(a,len,k);
	printf("位于第:%d 位\n",result); 
	

	return 0;
}

5.插入查找

#include<iostream>
#include<algorithm>
using namespace std;
int a[100];
int F[100]; 
int len ;
int k ;
int inter_Search(int *a,int n,int key)
{
	int low,high,mid;
	low=1;	/* 定义最低下标为记录首位 */
	high=n;	/* 定义最高下标为记录末位 */
	while(low<=high)
	{
		mid=low+ (high-low)*(key-a[low])/(a[high]-a[low]); /* 插值 */
		if (key<a[mid])		/* 若查找值比插值小 */
			high=mid-1;		/* 最高下标调整到插值下标小一位 */
		else if (key>a[mid])/* 若查找值比插值大 */
			low=mid+1;		/* 最低下标调整到插值下标大一位 */
		else
			return mid;		/* 若相等则说明mid即为查找到的位置 */
	}
	return 0;
}
int main()
{

	cout<<"请输入序列长度"<<endl;
	cin>>len; 
	cout<<"请输入查找的序列"<<endl;
	for(int i=1;i<=len;++i)
		cin>>a[i];
	cout<<"请输入要查找的数字"<<endl;
	cin>>k;
	int result=inter_Search(a,len,k);
	printf("位于第 %d 位\n",result);
	

	return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 暑假(补)-4

    动态规划算法是通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推(或者说分治)的方式去解决。 动态规划算法的基本思想与分治法类似,也是将待求解的问题...

    AngelNH
  • 西南民族大学程序竞赛

    No matter what activities you join,whether you want or not, you could gain unexp...

    AngelNH
  • 暑假(补)-5

    DFS全称Deep First Search,是一种遍历或搜索树或图的算法。在解决问题上,利用递归调用自身函数(这种说法好像不正确,领悟思想就好了)来实现搜索的...

    AngelNH
  • T4701 【卜卜】树状数组模板

    题目描述 在二维平面内给定n个点: 0 x y v表示给(x,y)的权值减去v 1 x y v表示给(x,y)的权值加上v 然后有m个操作 0 x y v ,...

    attack
  • TopcoderSRM679 Div1 250 FiringEmployees(树形dp)

    有一个 \(n\) 个点的树,每个点有点权(点权可能为负) ,求包含点\(1\)的最 大权连通子图(的权值和) 。 \(n \leqslant 2500\)

    attack
  • 1478. 安排邮筒 Krains 2020-07-30 14:51:32 动态规划DFS数学

    思路:将这条街分为几块区域,每个区域安排一个邮筒。在一个区域中,要想邮筒到该区域所有房子的距离之和最小,邮筒应该安排在这些房子位置的中位数上,这时邮筒到它们的距...

    Krains
  • 洛谷P2312 解方程(暴力)

    对于\(a[i]\)取模之后再判断就行了。注意判断可能会出现误差,可以多找几个模数

    attack
  • Leetcode 258. Add Digits

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan
  • 洛谷P2774 方格取数问题(最小割)

    attack
  • K-th Smallest Prime Fraction

    思路1: 一种聪明的做法,如果A = [1, 7, 23, 29, 47],那么有:

    用户1147447

扫码关注云+社区

领取腾讯云代金券