二分查找
二分查找(二分搜索)又称折半查找，它要求线性表是有序的，并且需要用一维数组进行存储。二分查找的基本思想如下：
假设L[low......high]为当前要查找的区间(假设是递增有序)。
(1)首先确定该区间的中间位置，mid=(low+high)/2;
(2)将待查找的key值与L[mid].key进行比较，如果相等，则查找结束；若不等，则在新的区间进行相同的操作，新的区间确定过程如下：
1)若key>L[mid].key，则key值只可能在mid的右边区间，则新的查找区间为L[mid+1,high];
2)若key<L[mid].key，则key值只可能在mid的左边区间，则新的查找区间为L[low,mid-1];
int BinarySearch(SeqList R,int low,int high,ElemType key)
{
int mid;
while(low<=high)
{
mid=low+(high-low)>>1; //可以有效地避免溢出的情况
if(key==R[mid].key)
return mid;
if(key<R[mid].key)
high=mid-1;
else
low=mid+1;
}
return -1;
}
递归实现：
int BinarySearch(SeqList R,int low,int high,ElemType key)
{
if(low>high)
return -1;
int mid=low+(high-low)>>1;
if(key==R[mid].key)
return mid;
else
{
if(key<R[mid].key)
BinarySearch(R,low,mid-1,key);
else
BinarySearch(R,mid+1,high,key);
}
}
![贤鱼的刷题日常--P1019 [NOIP2000 提高组] 单词接龙--题目详解](https://ucc.alicdn.com/images/user-upload-01/82396d7e07e7417eb32de7487afbd3d3.gif)
