网站的虚拟人怎么做的,清远市住房和城乡建设局门户网站,wordpress 搜索制作,无锡网络推广楚天软件本文来自#xff1a;C程序训练#xff1a;二分查找法的应用之2
在《C程序训练#xff1a;二分查找法的应用》一文中介绍了利用二分查找计算某个区间中数的个数#xff0c;本文介绍利用二分查找法计算数列中出现单个数字的位置。题目描述如下。
题目描述#xff1a;一维整…本文来自C程序训练二分查找法的应用之2
在《C程序训练二分查找法的应用》一文中介绍了利用二分查找计算某个区间中数的个数本文介绍利用二分查找法计算数列中出现单个数字的位置。题目描述如下。
题目描述一维整型数组a有N个(N是奇数)元素其中有一个元素值只出现一次其余元素值都出现2次且相邻。例如a[]{3,3,1,1,7,7,4,4,8}。值为8的元素只出现一次其余元素值都出现了2次且相邻。函数int find(int a[])的功能是使用二分查找方法找出这个只出现一次的元素并返回该元素的下标。编写程序找出这个数。设N1000。
输入格式
第一行读入一个整数n表示a中元素个数。
第二行读入n个整数表示数组a。
输出格式
输出找到的元素的位置和元素值。
样例1输入
9
3 3 1 1 7 7 4 4 8
样例1输出
8 8
样例2输入
11
5 5 -1 -1 -2 0 0 11 11 10 10
样例2输出
4 -2
编程思路
假设所有元素都出现两次且相邻那么我们可以按照一定的节奏给它们编号这个节奏就是0101……也就是说当元素第一次出现时我们称之为0第二次出现时称之为1。由于这些元素是相邻的所以我们可以通过0和1的交替来给它们打上节拍。
假设其中有一个元素丢失那么上述节奏被打乱了。因此我们可以按照二分查找来找到这个元素。例如数据如下表所示 前面成双成对的都是0、10、1这样的节奏对应的数据都是相等的当8出现时打破了这个僵局。所以我们在设计算法时第一次查寻如下图所示mid是偶数所指元素如果仍保留这种节奏下一次查寻区间在mid2与up之间查找否则查找区间在low与mid之间。针对该示例应在mid2与up之间查找。 继续查找如下图所示。这时mid指向奇数位置该位置的值与它上一个值比较如果仍保持这种节奏下一次查找区间应该在mid1与up之间否则查找区间应在low与mid之间。该示例应该在low与mid之间。 继续查找如下图所示。发现lowup不成立查找结束low或up即为找到的元素。 再举一个例子只提供图不再描述。 按上述思路编写程序即可。
源程序如下
#include stdio.hint find(int a[],int n)
{int low,up,mid;low0;upn-1;while(lowup){midlow(up-low)/2;if(mid%20)if(a[mid]a[mid1])lowmid2;elseupmid;else if(a[mid-1]a[mid])lowmid1;elseupmid-1;}return low;
}int main()
{int n;int a[1000];scanf(%d, n);for (int i 0; i n; i)scanf(%d, a[i]); int position find(a,n);printf(%d %d\n, position, a[position]);return 0;
}
参考资料
[1]李红卫李秉璋. C程序设计与训练第四版[M]大连大连理工大学出版社2023.
