二分查找又称折半查找
优点是比较次数少，查找速度快，平均性能好
缺点是要求待查表为有序表，且插入删除困难。
1.必须采用顺序存储结构 2.必须按关键字大小有序排列。
二分查找的基本思想是将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2],则找到x,算法中止；如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x.
时间复杂度无非就是while循环的次数！
n,n/2,n/4,....n/2^k（接下来操作元素的剩余个数），其中k就是循环的次数
由于你n/2^k取整后>=1 即令n/2^k=1 可得k=log2n,（是以2为底，n的对数） 所以时间复杂度可以表示O()=O(logn) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 int binSearch( const int *Array, int start, int end, int key) { int left,right; int mid; left=start; right=end; //注释中为递归算法，执行效率低，不推荐 /* mid=left+(right-left)/2; if(key<Array[mid]) { return(binSearch(Array,left,mid-1,key)); } else if(key>Array[mid]) { return(binSearch(Array,mid+1,right,key)); } else return mid; */ while (left<=right) { mid=(left+right)/2;// mid=left+(right-left)/2;更好，因为不会溢出 if (key==Array[mid]) return mid; else if (key<Array[mid]) right=mid-1; else if (key>Array[mid]) left=mid+1; } return -1; //找不到就返回-1 } 百度百科
折半查找效率分析： 基本操作：比较 最坏情况下，比较次数 C(n)=C( n/2)+1（n/2向下取整） C(1)=1 设n=2k，可解得 C(n)=k+1=log2n+1 于是 C(n)∈Θ(log2n)
通常称描述折半查找过程的二叉树为折半查找判定树。
长度为n的折半查找判定树的构造方法为： ⑴ 当n=0时，折半查找判定树为空； ⑵ 当n＞0时，折半查找判定树的根结点是有序表中序号为mid=(n+1)/2的记录，根结点的左子树是与有序表r[1] ~ r[mid-1]相对应的折半查找判定树，根结点的右子树是与r[mid+1] ~ r[n]相对应的折半查找判定树 ⑴ 折半查找判定树是一棵二叉排序树，即每个结点的值均大于其左子树上所有结点的值，小于其右子树上所有结点的值； ⑵ 折半查找判定树中的结点都是查找成功的情况，将每个结点的空指针指向一个实际上并不存在的结点——称为外结点，所有外结点即是查找不成功的情况，如图7-2(e)所示。如果有序表的长度为n，则外结点一定有n+1个。
在折半查找判定树中，某结点所在的层数即是查找该结点的比较次数，整个判定树代表的有序表的平均查找长度即为查找每个结点的比较次数之和除以有序表的长度。 在折半查找判定树中，查找不成功时的比较次数即是查找相应外结点时与内结点的比较次数。 整个判定树代表的有序表在查找失败时的平均查找长度即为查找每个外结点的比较次数之和除以外结点的个数。
对于一个有序数组，我们通常采用二分查找的方式来定位某一元素，请编写二分查找的算法，在数组中查找指定元素。
给定一个整数数组A及它的大小n，同时给定要查找的元素val，请返回它在数组中的位置(从0开始)，若不存在该元素，返回-1。若该元素出现多次，请返回第一次出现的位置。
测试样例： [1,3,5,7,9],5,3 返回：1 int getPos(vector<int> A, int n, int val) { // write code here int mid,start=0,end=n-1; if(n<1&&A.empty())return -1; while(start<end){ mid=(start+end)/2; if(A[mid]==val)end=mid; else if(A[mid]<val)start=mid+1; else if(A[mid]>val)end=mid-1; } if(A[start]==val)return start; else return -1; }