Java经典算法之折半查找（二分法）

采用二分法时，数据应是有序并且不重复的

与小时候玩的猜数游戏是一样的，会让你猜一个他所想的1~100之间的数，当你猜了一个数后，他会告诉你三种选择中的一个，比他想的大，或小，或猜中了，为了能用最少的次数猜中，必须从50开始猜，如果说你猜的小，那你必须从51~100开始猜，所以下一次猜的是75（51~100的一半），但如果他说有点大，则推出那个数在1~49之间，所以下一次猜25，每猜一次都将可能的值化为两部分

实现思想：假设数据是升序排序的，给一个定值x，从序列的中间位置开始查找，若x小于当前位置值，则在序列的前半段中查找，并再将数据一分为二

若x大于当前位置值，则在序列的后半段中查找，再将数据一分为二

若当前位置值等于x，则直接返回，如果没有找到则返回-1

实现代码：

public class Half {

    public static void main(String[] args) {
        int[] arr = new int[]{12, 23, 34, 45, 56, 67, 77, 89, 90};//length:9
        System.out.println(search(arr, 34));

    }

    public static int search(int[] arr, int key) {
        int start = 0;

        while (start <= end) {
            int middle = (start + end) / 2;//中间值:4,1,2
            if (key < arr[middle]) {
                end = middle - 1;
            } else if (key > arr[middle]) {
                start = middle + 1;
            } else {
                return middle;
            }
        }
        return -1;
    }
}

//输出2

巴特西

Java经典算法之折半查找（二分法）

最新文章

热门文章