二分查找法又称折半查找法，优点是比较次数少，查找速度快，平均查找性能好；其缺点是要求待查找的数据是有序的，且插入和删除时需移动大量数据。
假设一组有序数据（升序）存放在一维数组a中，采用二分查找法查找数据k的基本思想是：
将a数组中间位置的元素与待查找数k比较，如果两者相等，则查找成功；否则利用数组中间位置数据将数组分成前后两块，当中间位置的数据大于待查找数据k时，则下一步从前面一块查找k；当中间位置的数据小于待查找数据k时，下一步从后面一块查找k；重复以上过程，直至查找成功或失败。
下面两张图给出了用二分查找法查找数据22、45的具体过程，其中mid=(low high)/2，a[mid]表示数组中间位置的数据，当a[mid]>k时，修正high=mid-1；当a[mid]<k时，修正low=mid 1；当a[mid]=k时，表示查找成功；当high<low时，表示查找失败。初始状态：low=0，high=N-1。
当删除数据时，则该数据后面的数组元素往前移一位。
当插入数据时，则首先找到该数据插入的位置，并从最后一个数据元素开始向后移一位，直到空出该位置以作插入数据之用。
【编程示例】
从键盘输入N个有序整数，然后采用二分查找法在其中查找数据k，若找到，显示查找成功的信息，并将该数据删除；若没有找到，则将数据k插入到这些数中，插入操作后数据仍然有序。
源程序：
#include <stdio.h>
#define N 8
int main(void)
{
int a[N 1],k,i,low,high,mid;
int point;
printf("Please enter %d order data:",N);
for(i=0;i<N;i )
scanf("%d",&a[i]); //按从小到大的顺序输入数据
printf("Please enter the number to be located:");
scanf("%d",&k); //输入要查找的数据
low=0; high=N-1;
while(low<=high) //二分查找
{
mid=(low high)/2;
if(a[mid]==k)
{ point=mid; //记录查找值的位置
break;
}
else if(a[mid]<k) low=mid 1;
else high=mid-1;
}
if(low<=high) //如果查找成功则删除数据
{
printf("The index of data is: %d,Now delete it.\n",point); //显示查找值的下标
for(i=point;i<N;i ) //删除数据
a[i]=a[i 1];
for(i=0;i<N-1;i )
printf("M",a[i]);
printf("\n");
}
else //如果查找失败则插入数据
{
printf("The data is not in the array! Now insert.\n");
i=N-1;
while(i>=0 && a[i]>k) //查找并空出插入数据的位置
{
a[i 1]=a[i];
i=i-1;
}
a[ i]=k; //插入数据
for(i=0;i<=N;i )
printf("M",a[i]);
printf("\n");
}
return 0;
}
运行结果为：（查找成功，删除数据）
Please enter 8 order data: 23 45 67 89 96 98 123 125↙
Please enter the number to be located: 89↙
The index of data is: 3 , Now delete it.
23 45 67 96 98 123 125
运行结果为：（查找失败，插入数据）
Please enter 8 order data: 23 45 67 89 96 98 123 125↙
Please enter the number to be located: 70↙
The data is not in the array! Now insert.
23 45 67 70 89 96 98 123 125
此外，我还有其他较为简单的解释，首先要使用二分查找必须得先排序
/返回元素所在下标
int quick_find(int arr[], int begin, int end,int data)
{
if (begin > end)
{
//区间没有元素 没有找到
return -1;//返回值-1 没有找到
}
int mid = (begin end) >> 1;//中间
if (arr[mid] > data) return quick_find(arr, begin, mid-1, data);//往左边找
else if (arr[mid] < data) return quick_find(arr, mid 1, end, data);//往右边找
else return mid;
}
int main()
{
int arr[10] = { 110, 639, 44, 352, 878, 582, 297, 966, 422, 712 };
merge_sort(arr, 10);
for (int i = 0; i < 10; i)
{
printf("%d\t", arr[i]);
}
printf("\n 297的位置是%d", quick_find(arr, 0, 9, 297));
cin.get();
return 0;
}
返回的想找的数据的下标
