如何用二分查找法查找一个数组中的元素

二分查找又叫折半查找，但是有一个前提条件，就是你要查找的数据必须是按顺序储存，以关键字大小来排列的。
例如
如果是整形数组，存放0~9这10个数，数组必须按0到9（升序）或者9到0（降序）挨个储存。
如果你数组的元素之字符串，字符串的首字母就得按a~z或者z~a挨个储存，当最高位相同时比较次高位。
当你保证数组有序后，就可以开始执行二分查找了。
举个例子
1,3,6,8,9,10,11,15
如果你要查找的数字是10，查找过程如下
由于一共有7个元素，比较最中间的元素，即第四个，10>9，由于是升序排列，选择9的右边三个数进行比较,，这就将比较次数缩短了一半。在右半部分再去中间元素，即11,10<11，选取11左边部分进行比较，即和10进行比较，得到要找的元素。
当然也存在找不到的情况，比如找12，先与9比，范围缩小至右半部分，跟11比，在此基础上再缩小至现有右半部分，只剩一个15，不相等， 即没找到想要的元素。
这就是一个递归缩小范围的过程

假设有n个数已按照 升序（这是关键！） 放在一维数组a中，如何找到你想要的数呢？

二分法，顾名思义，把一段数字分成两半。
你要的数在 已经按照升序排好了 并且的情况下与中间数进行对比有4种情况：

为什么在发现数x比中间数大/小之后，设定left=mid+1和right=mid-1而不能是left=mid和right=mid

这就牵扯到如果中间数有两个（如示意图中的第一次循环的中间数为21、25），那么系统会自动选 左边 的那个数作为中间数（21）。
那么当需要检索的是 最末尾的数 ，而最后就剩两个边界，那么无论怎么取中间数，左右边界的范围都不会改变，左边界还是左边界。而你需要检索的数是右边界，即使数确实比中间数大，但是因为算法，中间数永远都不会是右边界，所以永远都不会找到右边界的数。

但是如果设定为left=mid+1和right=mid-1，这种情况就能够使左边界=右边界，中间数就等于那个数，从而能够进行比较、找到。

二分查找的基本思想是：（设R[lowhigh]是当前的查找区间）
（1）首先确定该区间的中点位置：mid=(low+high)/2
（2）然后将待查的K值与R[mid]key比较：若相等，则查找成功并返回此位置，否则须确定新的查找区间，继续二分查找
//
Source：
public
int
search(int[]
q)
{
int
i,
low
=
0,
high
=
qLength
-
1,
middle;
ConsoleWrite("请输入想要查找的数字:");
i=intParse(ConsoleReadLine());
while
(low
<=
high)
{
middle
=
(low
+
high)
/
2;
if
(i
==
q[middle])return
i;
if
(i
<
q[middle])high
=
middle
-
1;
else
low
=
middle
+
1;
}
throw
new
Exception("数组中不存在这个数。");
}

总共13个，从0开始，最大是12，使用二分法原则分析如下
第一次：12/2=6 , (6)=45<90
第二次:(7+12)/2=9,(9)=77<90
第三次:(10+12)/2=11,(11)=95>90
第四次:((11-1)+10)/2=10,(10)=90 查找成功

二分查找的核心就是在于逐渐逼近（有点夹逼定理的感觉），从有序数组的两边，逐渐的向所要查找的元素周围逼近，最终锁定元素。

二分查找每一次的查找都会减少当前锁定范围的一半，因此时间复杂度为：
下一篇： 写给媳妇儿的算法（二）——2-opt算法解决商旅问题

---