其实二分法查找算法已经太常见了，但是很多时候知道思路和真正实现还是有一定的差距的，这里做个纪念
其实就是对一个给定的经过排序的集合，假设该数组的长度是N那么二分后是N/2，再二分后是N/4……直到二分到1结束，当然这是属于最坏的情况，
即使每次找到的那个中点数都不是我们要找的，那么二分的次数就是基本语句执行的次数，于是我们可以设次数为x，N*（1/2）^x=1；则x=logn,底数是2，因此查询效率是非常高的。
伪代码是这样：
假定数组是经过从小到大的位置排序的，通常定义4个变量
L：指向数组左侧起始位置的指针
R：指向数组右侧终止位置的指针
M：L 和 R的的中间位置
V：给定的值
通过比较V和M指向的值
while(L <= R )
if ( V 小于 M指向的值 )
R 向左移动
if ( V 大于 M 指向的值)
L 向右移动
if V 等于 M 指向的值
直接返回M的索引值
没找到则返回-1
下面是用java实现的代码
/**
* 非递归的二分法查找
* @author linda
*
*/
public class BinarySearch {
public static void main(String[] args) {
int[] dataArray={10,20,30,40,50,60,70,80,90,100,135,147};
int index = binarySearcy(dataArray,70);
System.out.println("index="+index);
}
private static int binarySearcy(int[] array ,int value){
int b = 0; //左侧指针
int e = array.length;//右侧指针
int m = 0; //中间位置
while( b <= e){
m = b + ( e - b )/2; //计算出中间位置
//如果找到了，立刻返回索引值
if (value == array[m]){
return m;
}else if( value < array[m]){//当前位置的值小于给定的值，把右侧指针左移
e = m - 1;
}else{
b = m + 1; //当前位置的值大于给定的值，把左侧的指针右移
}
}
return -1;
}
}
下面是用python 实现的代码
def binary_search(array,value):
b = 0
m = -1
e = len(array)
while( b <= e ):
m = b + ( e - b) / 2
if value == array[m]:
return m
elif value < array[m]:
e = m - 1
else:
b = m + 1
return -1
arr=[10,20,30,40,50,60,70,80,90,100,135,147]
s = 135
index = binary_search(arr,s)
print(index)