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

青山师

发布于 2023-05-05 17:32:36

1440

发布于 2023-05-05 17:32:36

文章被收录于专栏：IT当时语_青山师_JAVA技术栈

二分搜索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
    }


}

运行结果如下：