二分搜索BinarySearch的 “来龙去脉”
二分搜索用于检索某个key是否在已排好序的序列中，我们还记得上编程语言的基础课程：猜字游戏吗？
猜字游戏第一版： 程序预先选取一个数字作为猜想的目标； 用户键盘输入自己猜想的数字； 如果不相等则提示错误； 如果猜对了则游戏终止。
这个游戏猜想效率是很低的。因为这个笨拙的游戏规则只会告诉你是对的还是错误的！！！然后你得进行下一次的瞎猜…
猜字游戏第二版： 程序预先选取一个数字（假设是40）作为猜想的目标； 用户键盘输入自己猜想的数字（假设是5）； 如果不相等则提示错误，并且有内容：您猜的太小了； 然后用户输入20，还是提示错误：您猜的太小了； 用户再试探，输入50，提示错误：您猜的太大了； 用户输入40（假设运气好），提示正确，结束游戏。 第二版的游戏相比第一版增加了游戏提示，这个提示有利于用户缩小下一次猜想的数字的大概范围。
我们的二分搜索就可以认为来自这个猜想，思路是： 在有序数组中查找关匹配键字的元素。 获取最大索引 hi、最小索引 lo； 找到中间索引 mid = (hi lo) / 2； 关键字key去和中间索引值比较arr[mid]； 这里的关键字key就类似我们猜字游戏中的40； 如果如果中间索引值arr[mid] > key，则表明key在中间索引的左边，类似于猜字游戏中用户猜的数字大了，需要往小的方向猜。 如果中间索引值arr[mid] < key，则表名key在中间索引的右边，猜的数字比较小，需要往大的方向猜。
代码语言：javascript复制package org.byron4j.dsaa.basic;
/**
* 二分检索--用于检索已排好序的序列
* @author BYRON.Y.Y
*
*/
public class BinarySerach {
/**
* 在有序数组sortedArr中，检索是否存在key，存在则返回索引位置index，否则返回-1
* @param sortedArr
* @param key
* @return
*/
public static int index(int[] sortedArr, int key) {
int lo = 0;//低位索引值
int hi = sortedArr.length - 1;//高位索引值
int mid = (hi lo) / 2;//中间索引值
while( hi >= lo ) {
if( sortedArr[mid] > key ) {
//中间值大于key，则说明key在中间值前面，高位减一
hi = mid - 1;
}else if( sortedArr[mid] < key ){
//中间值小于key，则说明key在中间值后面，低位加一
lo = mid 1;
}else {
return mid;
}
//重新计算中间索引位置
mid = (hi lo) / 2;
}
return -1;
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6};
System.out.println(index(arr, 1));//0
System.out.println(index(arr, 2));//1
System.out.println(index(arr, 3));
System.out.println(index(arr, 4));
System.out.println(index(arr, 5));
System.out.println(index(arr, 6));//5
System.out.println(index(arr, 7));//-1
System.out.println(index(arr, -1));//-1
}
}运行结果如下：
代码语言：javascript复制0
1
2
3
4
5
-1
-1
