二分搜索 Binary search

二分搜索 Binary search

二分搜索也是比较常见的,在生活中的应用尤其广泛。比如在酒桌上玩猜数字,一个人坐庄先准备一个在一定范围内的数字,其余每个人轮流猜一次,庄说出是大了还是小了,说中的人喝。这个游戏玩过的人应该不少,其中肯定有许多人都是从中间开始猜,认为这样是比较快的排除方法。是的,这就是二分搜索。

二分搜索对于查找对象有要求,即有序。原理就是取其中间进行判断,如果未找到,则根据顺序关系再分别对两边其中的一个子区进行再次查找,直到找到或者未发现,搜索结束。

public static void main(String[] args) {
    int[] array = {1, 12, 13, 27, 34, 38, 49, 50, 64, 65, 76, 78, 97};
    int target = 50;
    System.out.println("result index:" + binarySearch(array, target));
}

public static int binarySearch(int[] arr, int target) {
    int startPosition = 0;  // 设置搜索的上下界
    int endPosition = arr.length - 1;

    while (startPosition <= endPosition) {  // 在搜索过程中,会逐渐缩小搜索范围
        int midPosition = (startPosition + endPosition) / 2;  // 确定中间
        if (arr[midPosition] == target) {  // 找到则返回下标
            return midPosition;
        } else if (arr[midPosition] < target) {  // 当目标值比中间值大时,则在后区(大区)搜索
            startPosition = midPosition + 1;
        } else {  // 当目标值比中间值小时,则在前区(小区)搜索
            endPosition = midPosition - 1;
        }
    }
    return -1; // 未找到则返回-1
}

发表评论