|
二分查找(二分搜索)又称折半查找，它要求线性表是有序的，并且需要用一维数组进行存储。二分查找的基本思想如下： 假设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);
- }
- }
出处：http://www.cnblogs.com/dolphin0520/
本博客中未标明转载的**归作者Matrix海子和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在**页面明显位置给出原文连接，否则保留追究法律责任的权利。
| 
楼主
