二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
在二分查找的应用中，可以是单纯的查找某一个元素，也可以查找该元素的上下界。其代码模板如下：
1 int searc(int k) 2 { 3 int low = 0,high = n-1,mid; 4 while(low <= high) 5 { 6 mid = (low + high)/2; 7 if(a[mid] == k) 8 return mid; 9 else if(a[mid] < k) 10 { 11 low = mid + 1; 12 } 13 else 14 high = mid - 1; 15 } 16 return 0; 17 }
这是单纯的查找元素，若有这个元素，则返回元素的下标，若没有，则返回0.注意，mid是元素的下标，k是要查找的数，注意不要混淆。
接下来是一道关于二分查找上下界的题目
8 4 1 2 3 4 5 6 8 11 4 9 2 7
4 8 2 6 8
1 #include <stdio.h> 2 #include <math.h> 3 #include<algorithm> 4 using namespace std; 5 6 int shu[10000000],n; 7 8 int searc1(int k) 9 { 10 int low = 0,right = n-1,mid; 11 while(low < right) 12 { 13 mid = (low + right + 1)/2; 14 if(shu[mid] <= k) 15 { 16 low = mid; 17 } 18 else 19 right = mid - 1; 20 } 21 return low; 22 } 23 int searc2(int k) 24 { 25 int low = 0,right = n-1,mid; 26 while(low < right) 27 { 28 mid = (low + right)/2; 29 if(shu[mid] >= k) 30 { 31 right = mid; 32 } 33 else 34 low = mid + 1; 35 } 36 return low; 37 } 38 int main() 39 { 40 int m,i,j,k; 41 while(scanf("%d%d",&n,&m)!=EOF) 42 { 43 for(i = 0;i<n;i++) 44 scanf("%d",&shu[i]); 45 sort(shu,shu+n); 46 for(i = 0;i<m;i++) 47 { 48 scanf("%d",&k); 49 int ans1 = searc1(k); 50 int ans2 = searc2(k); 51 if(shu[ans1] == shu[ans2] || k - shu[ans1] < shu[ans2] - k) 52 printf("%d\n",shu[ans1]); 53 else if(k - shu[ans1] > shu[ans2] - k) 54 printf("%d\n",shu[ans2]); 55 else if(k - shu[ans1] == shu[ans2] - k) 56 printf("%d %d\n",shu[ans1],shu[ans2]); 57 } 58 printf("\n"); 59 } 60 return 0; 61 }
原文：http://www.cnblogs.com/codeball/p/3627512.html