本文来自：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;
      else
        up=mid;
    else if(a[mid-1]==a[mid])
      low=mid+1;
    else
      up=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.