二分搜索BinarySearch的"来龙去脉"

爱被打了一巴掌 2022-05-22 00:27 156阅读 0赞

### 二分搜索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在中间索引的右边，猜的数字比较小，需要往大的方向猜。

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
        }
    
    
    }

运行结果如下：

0
    1
    2
    3
    4
    5
    -1 -1