面试过程中遇到这个问题
首先我先想到的是 二分查找
但是二分查找，是需要有序的
所以先将数组 有序排列（冒泡排序）
再进行二分查找
冒泡排序：（相邻比逆法，基本思想是，两两比较相邻记录的关键字，如果反序，则交换，直到没有反序的记录为止）
void bubbleSort（SqList *L）{
int i，j；
Status flag = TRUE; //flag用来标记
for(i=1;i<L->length&&flag;i++)//若flag为true，则退出循环
{
flag = FALSE；
for(j=L->length -1;j>=1;j--){
if(L->r[j] > L->r[j+1]){
sway(L,j,j+1);
flag=TRUE;
}
}
}
}
二分查找：（前提是 线性表的记录必须是关键有序，基本思想是，在有序表中，取中间记录作为比较对象，若给定的值与中间记录的关键字相等，则查找成功；若给定的值小于中间记录的关键字，则在中间记录的左半区进行查找；若大于，在右半区进行查找，不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止）
int Binary_Search(int *a,int n,int key){
int low,high,mid;
low = 1;
high = n;
while(low<=high){
mid = (low+high)/2;
if(key < a[mid])
high=mid - 1;
else if(key > a[mid])
low = mid + 1;
else
return mid;
}
return 0;
}
原文：https://www.cnblogs.com/darcy-hui/p/13261511.html