折半查找法（half-interval search）
优点：比较次数少，查找速度快，平均性能好
缺点：是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
注意：折半查找法仅适用于对已有顺序的数组、数据进行操作！！！
例如：要在数组arr[]={8,7,9,6,4,1,2,5,3,10,11};中查找key=7的位置；首先，我们要先将数组arr中的数据成员进行排序。arr[]={1,2,3,4,5,6,7,8,9,10,11};
如图所示：将该组数据小端记作low，大端记作high,中间值记作mid;
二分法查找时，将所查找的key与mid比较，例如key=7，即可缩小查找范围在mid和high之间；
如图所示即可找到key=low=7;
注意：（敲黑板）如果中间数mid不是整数，需要进行取整。
C语言实现：
#include<stdio.h>
int BinSearch(int arr[],int len,int key) //折半查找法（二分法）
{int low=0; //定义初始最小int high=len-1; //定义初始最大int mid; //定义中间值while(low<=high){mid=(low+high)/2; //找中间值if(key==arr[mid]) //判断min与key是否相等return mid; else if(key>arr[mid]) //如果key>mid 则新区间为[mid+1,high]low=mid+1;else //如果key<mid 则新区间为[low,mid-1]high=mid-1;}return -1; //如果数组中无目标值key，则返回 -1 ；
}
int main()
{int arr[]={1,2,3,4,5,6,7,8,9,10,11}; //首先要对数组arr进行排序printf("%d \n",BinSearch(arr,(sizeof(arr)/sizeof(arr[0])),7));return 0;
}c++实现：
#include<iostream>
#include<string>
#include<Windows.h>
#include<cstring>
#define MAXN 10010
using namespace std;
int main()
{int n, val;int a[MAXN];int st, en, mid;cin >> n;st = 1;en = n;for (int i = 1;i <= n;i++) cin >> a[i];cin >> val;while (st <= en){mid = (st + en) >> 1;if (a[mid] == val) {cout << mid << endl;system("pause");return 0;}else if (a[mid] > val) {en = mid - 1;}else st = mid + 1;}cout << "-1" << endl;system("pause");return 0;
}
