C程序训练：二分查找法的应用之2
本文来自：C程序训练：二分查找法的应用之2
在《C程序训练：二分查找法的应用》一文中介绍了利用二分查找计算某个区间中数的个数，本文介绍利用二分查找法计算数列中出现单个数字的位置。题目描述如下。
题目描述：一维整型数组a有N个(N是奇数)元素，其中有一个元素值只出现一次，其余元素值都出现2次，且相邻。例如a[]={3,3,1,1,7,7,4,4,8}。值为8的元素只出现一次，其余元素值都出现了2次，且相邻。函数int find(int a[])的功能是使用二分查找方法，找出这个只出现一次的元素，并返回该元素的下标。编写程序找出这个数。设N<1000。
输入格式：
第一行读入一个整数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
编程思路：
假设所有元素都出现两次且相邻，那么我们可以按照一定的节奏给它们编号，这个节奏就是0，1，0，1，……也就是说，当元素第一次出现时我们称之为0，第二次出现时称之为1。由于这些元素是相邻的，所以我们可以通过0和1的交替来给它们打上节拍。
假设其中有一个元素丢失，那么，上述节奏被打乱了。因此我们可以按照二分查找来找到这个元素。例如，数据如下表所示：
前面成双成对的都是0、1，0、1这样的节奏对应的数据都是相等的，当8出现时，打破了这个僵局。所以我们在设计算法时，第一次查寻如下图所示，mid是偶数，所指元素如果仍保留这种节奏，下一次查寻区间在mid+2与up之间查找，否则，查找区间在low与mid之间。针对该示例，应在mid+2与up之间查找。
继续查找，如下图所示。这时mid指向奇数位置，该位置的值与它上一个值比较，如果仍保持这种节奏，下一次查找区间应该在mid+1与up之间，否则，查找区间应在low与mid之间。该示例应该在low与mid之间。
继续查找，如下图所示。发现low<up不成立，查找结束，low或up即为找到的元素。
再举一个例子，只提供图，不再描述。
按上述思路编写程序即可。
源程序如下：
#include <stdio.h>int find(int a[],int n)
{int low,up,mid;low=0;up=n-1;while(low<up){mid=low+(up-low)/2;if(mid%2==0)if(a[mid]==a[mid+1])low=mid+2;elseup=mid;else if(a[mid-1]==a[mid])low=mid+1;elseup=mid-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.