【算法】001-二分查找

一时失言乱红尘 2023-10-05 07:27 11阅读 0赞

# 一、生活案例 #

## 1、找出学号为52的学生的试卷 ##

一个班级100名学生的100张试卷按照1号到100号从上往下的顺序放在桌子上，你现在需要找出学号为52的学生的试卷，是从第一张开始一张一张得找吗？显然不是，而是从最中间开始找，因为这距离52号试卷更近！

我们将从第一张试卷开始往下找这种方式称之为**简单查找**，将从中间开始找这种方式称之为**二分查找（二分法）**；

## 2、找出学号为25的学生的试卷 ##

如上面的条件，这次我们查找第25号学生的试卷，我们使用**二分法**进行查找，我们先将所有时间分成两份，再讲第一份试卷分成两份，这样我们就很快地找到学号为25的学生的试卷；

## 3、猜数字 ##

小红随便写了一个1到100之内的数字，假定为39，让小兰去猜。当小兰猜一个数字的时候，如果没猜对小红只能说是大了还是小了，那么小兰怎么以最快的方式猜到39呢？使用“简单查找”的思想是从1一直猜，直到39为止，需要猜39次。但使用“二分查找”的思想，就是先猜50，小红说大了，就猜25，小红说小了，就再猜33，以此类推，直到猜到39为止，经过测试我们得知仅需要猜7次！

# 二、一个故事 #

## 1、一个百万富翁的故事 ##

一个叫杰米的百万富翁，一天，碰上一件奇怪的事，一个叫韦伯的人对他说，我想和你定个合同，我将在整整一个月中每天给你10万元，而你第一天只需给我一分钱，而后每一天给我的钱是前一天的两倍。杰米说：“真的？！你说话算数？”

合同开始生效了，杰米欣喜若狂。第一天杰米支出一分钱，收入10万元；第二天，杰米支出2分钱，收入10万元；第三天，杰米支出4分钱，收入10万元；第四天，杰米支出8分钱，收入10万元。。。。。。到了第十天，杰米共得到200万元，而韦伯才得到1048575分，共10000元多点。杰米想：要是合同定两个月，三个月多好！可从第21天起，情况发上了变化。

第21天，杰米支出1万多，收入10万元。到第28天，杰米支出134万多，收入10万元。结果杰米在一个月（31天）内得到310万元的同时，共付给韦伯2147483647分，也就是2000多万元！杰米破产了。

## 2、对，我们说的就是指数函数 ##

x还是怎么跑，y就上天了！

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70][]

## 3、对数函数 ##

x跑十万八千里了，y也就刚刚走两步！

（图片不严谨）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 1][]

## 4、我们学到了什么 ##

**指数型增长速度极快！指数型下降当然也是速度极快！**

**二分查找就是一种指数型下降！**

## 5、二分法——运用指数的力量、对数的规律 ##

从100中找出39需要7次，从100000000中找出37826562需要多少次？答案是27次！

这就是恐怖之所在！

# 三、代码实现 #

## 1、小兰猜数字（100内） ##

### 代码实现： ###

package com.zibo;
    
    //二分查找
    public class BinarySearch {
        public static void main(String[] args) {
            //小红的数字39
            int x = 39, max = 100, min = 1,times = 0;
            System.out.println("小红：大家好，最小值为" + min + "，最大值为" + max + "我说的数字是39，别告诉小兰哦！");
            System.out.println("小兰：我会二分法，我怕什么！");
            System.out.println("开始猜：");
            //二分法猜数字
            int currentNum;
            do {
                times++;
                currentNum = max - (max - min + 1) / 2;//24
                System.out.println("小兰：我猜" + currentNum);
                if(currentNum > x){
                    System.out.println("小红：" + currentNum + "大了");
                    System.out.println("小兰脑子里想：最大值的可能性从" + max + "改为" + (currentNum - 1));
                    max = currentNum - 1;
                }else if(currentNum < x) {
                    System.out.println("小红：" +currentNum + "小了");
                    System.out.println("小兰脑子里想：最小值的可能性从" + min + "改为" + (currentNum + 1));
                    min = currentNum + 1;
                }
            }while (currentNum!=x);
            System.out.println("小红：恭喜你，你猜对了");
            System.out.println("小红：你真厉害，只用了" + times + "次！");
            System.out.println("小兰：小意思！");
        }
    }

### 运行结果： ###

小红：大家好，最小值为1，最大值为100我说的数字是39，别告诉小兰哦！
    小兰：我会二分法，我怕什么！
    开始猜：
    小兰：我猜50
    小红：50大了
    小兰脑子里想：最大值的可能性从100改为49
    小兰：我猜25
    小红：25小了
    小兰脑子里想：最小值的可能性从1改为26
    小兰：我猜37
    小红：37小了
    小兰脑子里想：最小值的可能性从26改为38
    小兰：我猜43
    小红：43大了
    小兰脑子里想：最大值的可能性从49改为42
    小兰：我猜40
    小红：40大了
    小兰脑子里想：最大值的可能性从42改为39
    小兰：我猜38
    小红：38小了
    小兰脑子里想：最小值的可能性从38改为39
    小兰：我猜39
    小红：恭喜你，你猜对了
    小红：你真厉害，只用了7次！
    小兰：小意思！

## 2、小兰猜数字（100000000内） ##

### 代码实现： ###

package com.zibo;
    
    //二分查找
    public class BinarySearch {
        public static void main(String[] args) {
            //小红的数字39
            int x = 37826562, max = 100000000, min = 1,times = 0;
            System.out.println("小红：大家好，最小值为" + min + "，最大值为" + max + "我说的数字是39，别告诉小兰哦！");
            System.out.println("小兰：我会二分法，我怕什么！");
            System.out.println("开始猜：");
            //二分法猜数字
            int currentNum;
            do {
                times++;
                currentNum = max - (max - min + 1) / 2;//24
                System.out.println("小兰：我猜" + currentNum);
                if(currentNum > x){
                    System.out.println("小红：" + currentNum + "大了");
                    System.out.println("小兰脑子里想：最大值的可能性从" + max + "改为" + (currentNum - 1));
                    max = currentNum - 1;
                }else if(currentNum < x) {
                    System.out.println("小红：" +currentNum + "小了");
                    System.out.println("小兰脑子里想：最小值的可能性从" + min + "改为" + (currentNum + 1));
                    min = currentNum + 1;
                }
            }while (currentNum!=x);
            System.out.println("小红：恭喜你，你猜对了");
            System.out.println("小红：你真厉害，只用了" + times + "次！");
            System.out.println("小兰：小意思！");
        }
    }

### 运行结果： ###

小红：大家好，最小值为1，最大值为100000000我说的数字是39，别告诉小兰哦！
    小兰：我会二分法，我怕什么！
    开始猜：
    小兰：我猜50000000
    小红：50000000大了
    小兰脑子里想：最大值的可能性从100000000改为49999999
    小兰：我猜25000000
    小红：25000000小了
    小兰脑子里想：最小值的可能性从1改为25000001
    小兰：我猜37500000
    小红：37500000小了
    小兰脑子里想：最小值的可能性从25000001改为37500001
    小兰：我猜43750000
    小红：43750000大了
    小兰脑子里想：最大值的可能性从49999999改为43749999
    小兰：我猜40625000
    小红：40625000大了
    小兰脑子里想：最大值的可能性从43749999改为40624999
    小兰：我猜39062500
    小红：39062500大了
    小兰脑子里想：最大值的可能性从40624999改为39062499
    小兰：我猜38281250
    小红：38281250大了
    小兰脑子里想：最大值的可能性从39062499改为38281249
    小兰：我猜37890625
    小红：37890625大了
    小兰脑子里想：最大值的可能性从38281249改为37890624
    小兰：我猜37695312
    小红：37695312小了
    小兰脑子里想：最小值的可能性从37500001改为37695313
    小兰：我猜37792968
    小红：37792968小了
    小兰脑子里想：最小值的可能性从37695313改为37792969
    小兰：我猜37841796
    小红：37841796大了
    小兰脑子里想：最大值的可能性从37890624改为37841795
    小兰：我猜37817382
    小红：37817382小了
    小兰脑子里想：最小值的可能性从37792969改为37817383
    小兰：我猜37829589
    小红：37829589大了
    小兰脑子里想：最大值的可能性从37841795改为37829588
    小兰：我猜37823485
    小红：37823485小了
    小兰脑子里想：最小值的可能性从37817383改为37823486
    小兰：我猜37826537
    小红：37826537小了
    小兰脑子里想：最小值的可能性从37823486改为37826538
    小兰：我猜37828063
    小红：37828063大了
    小兰脑子里想：最大值的可能性从37829588改为37828062
    小兰：我猜37827300
    小红：37827300大了
    小兰脑子里想：最大值的可能性从37828062改为37827299
    小兰：我猜37826918
    小红：37826918大了
    小兰脑子里想：最大值的可能性从37827299改为37826917
    小兰：我猜37826727
    小红：37826727大了
    小兰脑子里想：最大值的可能性从37826917改为37826726
    小兰：我猜37826632
    小红：37826632大了
    小兰脑子里想：最大值的可能性从37826726改为37826631
    小兰：我猜37826584
    小红：37826584大了
    小兰脑子里想：最大值的可能性从37826631改为37826583
    小兰：我猜37826560
    小红：37826560小了
    小兰脑子里想：最小值的可能性从37826538改为37826561
    小兰：我猜37826572
    小红：37826572大了
    小兰脑子里想：最大值的可能性从37826583改为37826571
    小兰：我猜37826566
    小红：37826566大了
    小兰脑子里想：最大值的可能性从37826571改为37826565
    小兰：我猜37826563
    小红：37826563大了
    小兰脑子里想：最大值的可能性从37826565改为37826562
    小兰：我猜37826561
    小红：37826561小了
    小兰脑子里想：最小值的可能性从37826561改为37826562
    小兰：我猜37826562
    小红：恭喜你，你猜对了
    小红：你真厉害，只用了27次！
    小兰：小意思！

# 四、思考总结 #

## 1、二分法的本质 ##

是对指数函数的逆向运用；

## 2、注意 ##

**二分查找的对象必须是有序的；**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020091816370954.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200918164357166.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz,size_16,color_FFFFFF,t_70