差点儿被妹子难住的我

今天差点儿被妹子难住了,具体情况容我慢慢说

什么是二分查找呢

前几天中午吃饭间隙,团队里面的妹子突然问我,什么是二分查找。

搞得阿粉有点儿懵,什么意思,这是在考我?那我如果说出来二分查找的定义岂不是显得我太书生气,不有趣?这不符合阿粉的性格啊,突然脑子一激灵有了主意。

阿粉:在说二分查找之前,不如咱们来玩个游戏。我身上穿的这件短袖价钱在 100 以内,你猜猜实际上它的价格是多少?你随便说数字,如果说多了我会说你说多了,如果说少了我也会如实回答,知道你答对了为止。

妹子: 100 以内?是 50 吗?

阿粉:你说少了,再猜猜。

妹子: 75 ?

阿粉:说少了,你再猜。

妹子: 88 ?

阿粉:这次猜对了呦!你再仔细看看你猜的过程,刚开始猜测是 50 ,为什么不是其他数字呢?

妹子:因为你说价钱在 100 以内,如果说 50 的话,你告诉我多了,那小于 50 的数字我就不用 care 了,如果是少了,那大于 50 的数字我就不用猜了,这样相对来说就能更快的猜到正确答案。

阿粉:你这样的思想,就体现了二分查找啊。二分查找的过程就是,从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较;直到找到要找的数字为止。当然了,在这个过程中,你也可能是找不到要找的数字的。

妹子:哦,原来这就是二分查找啊,还是挺简单的,哈哈哈哈

阿粉:它可不简单啊,你如果不信,可以写写代码试试,看看能不能实现出来。

阿粉刚说完就看到了妹子在努力敲代码中

一会儿,妹子就把代码写出来了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

public static int binarySearch(int[] arr, int n, int value){
    int low = 0;
    int high = n-1;

    while (low <= high){
		// 定义中间数值 mid 
        int mid = low + (( high - low) >> 1);
		// 如果 arr[mid] == value ,则此时的中间数即为所求,直接返回即可
		// 如果 arr[mid] != value ,就更改取值范围
        if ( arr[mid] == value){
            return mid;
        }else if( arr[mid] < value){
            low = mid + 1;
        }else{
            high = mid - 1;
        }
    }
	// while 循环结束仍然没有找到要求的数字,那就是没有
    return -1;
}

public static void main(String[] args){
    int[] arr ={1,37,8,27,13,66,25,30,47,95};

    // 调用 BinarySearch 
    int binarySearch = binarySearch(arr,arr.length,27);

    System.out.println(binarySearch);
}

妹子:阿粉小哥哥,为啥我写的程序不对呢,明明数组里面有 27 ,为什么运行结果给我的值是 -1 呢

阿粉一看,还真的是,怎么回事儿,明明 binarySearch 那部分代码写的一点儿毛病都没有,怎么就是运行不出来呢,阿粉看的满头大汗的

突然阿粉看到妹子定义的数组,顿时明白了。

阿粉:你知道使用二分查找的前提吗?

妹子:啥玩意儿?咋还有前提条件呢?刚刚你可没跟我说啊

阿粉:咱们再回到刚刚一起做的游戏里面去,刚开始你就猜 50 ,然后大于 50 的话,小于 50 的咱们就不考虑对不对,那么咱们是不是就默认整个数组是有序的,所以咱们才可以不用管小于 50 的数了,对吗?

妹子:你这么一说,果然是啊。所以我定义的数组不是有序的,二分查找这个数组的时候,就会去查 13 ,我要查找的数字是 27 ,大于 13 ,所以程序就往后面查找去了,但是后面已经没有 27 了,所以会给我返回 -1

阿粉:对!你这个小脑袋瓜也太聪明了吧。把数组里面的数字变成有序就可以得到你想要的结果了。

妹子:哇塞,阿粉小哥哥,真的诶,程序返回给我正确的结果了。你可真是太棒了吧

阿粉被夸的又脸红了。。。

关于二分查找,各位看官们 get 了吗~

Java Geek Tech wechat
欢迎订阅 Java 极客技术,这里分享关于 Java 的一切。