【算法】001

【算法】001

一、生活案例

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

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

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

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

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

、猜数字

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

二、一个故事

1、一个百万富翁的故事

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

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

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

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

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

、对数函数

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

（图片不严谨）

4、我们学到了什么

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

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

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

从100中出9需要7次，从100000000中出7826562需要多少次？答案是27次！

这就是恐怖之所在！

三、代码实现

1、小兰猜数字（100内）

代码实现：

代码语言：javascript代码运行次数：0运行复制

package com.zibo;

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

运行结果：

代码语言：javascript代码运行次数：0运行复制

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

2、小兰猜数字（100000000内）

代码实现：

代码语言：javascript代码运行次数：0运行复制

package com.zibo;

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

运行结果：

代码语言：javascript代码运行次数：0运行复制

小红：大家好，最小值为1，最大值为100000000我说的数字是9，别告诉小兰哦！
小兰：我会二分法，我怕什么！
开始猜：
小兰：我猜50000000
小红：50000000大了
小兰脑子里想：最大值的可能性从100000000改为49999999
小兰：我猜25000000
小红：25000000小了
小兰脑子里想：最小值的可能性从1改为25000001
小兰：我猜7500000
小红：7500000小了
小兰脑子里想：最小值的可能性从25000001改为7500001
小兰：我猜4750000
小红：4750000大了
小兰脑子里想：最大值的可能性从49999999改为4749999
小兰：我猜40625000
小红：40625000大了
小兰脑子里想：最大值的可能性从4749999改为40624999
小兰：我猜9062500
小红：9062500大了
小兰脑子里想：最大值的可能性从40624999改为9062499
小兰：我猜8281250
小红：8281250大了
小兰脑子里想：最大值的可能性从9062499改为8281249
小兰：我猜7890625
小红：7890625大了
小兰脑子里想：最大值的可能性从8281249改为7890624
小兰：我猜769512
小红：769512小了
小兰脑子里想：最小值的可能性从7500001改为76951
小兰：我猜7792968
小红：7792968小了
小兰脑子里想：最小值的可能性从76951改为7792969
小兰：我猜7841796
小红：7841796大了
小兰脑子里想：最大值的可能性从7890624改为7841795
小兰：我猜781782
小红：781782小了
小兰脑子里想：最小值的可能性从7792969改为78178
小兰：我猜7829589
小红：7829589大了
小兰脑子里想：最大值的可能性从7841795改为7829588
小兰：我猜782485
小红：782485小了
小兰脑子里想：最小值的可能性从78178改为782486
小兰：我猜782657
小红：782657小了
小兰脑子里想：最小值的可能性从782486改为782658
小兰：我猜782806
小红：782806大了
小兰脑子里想：最大值的可能性从7829588改为7828062
小兰：我猜782700
小红：782700大了
小兰脑子里想：最大值的可能性从7828062改为7827299
小兰：我猜7826918
小红：7826918大了
小兰脑子里想：最大值的可能性从7827299改为7826917
小兰：我猜7826727
小红：7826727大了
小兰脑子里想：最大值的可能性从7826917改为7826726
小兰：我猜782662
小红：782662大了
小兰脑子里想：最大值的可能性从7826726改为782661
小兰：我猜7826584
小红：7826584大了
小兰脑子里想：最大值的可能性从782661改为782658
小兰：我猜7826560
小红：7826560小了
小兰脑子里想：最小值的可能性从782658改为7826561
小兰：我猜7826572
小红：7826572大了
小兰脑子里想：最大值的可能性从782658改为7826571
小兰：我猜7826566
小红：7826566大了
小兰脑子里想：最大值的可能性从7826571改为7826565
小兰：我猜782656
小红：782656大了
小兰脑子里想：最大值的可能性从7826565改为7826562
小兰：我猜7826561
小红：7826561小了
小兰脑子里想：最小值的可能性从7826561改为7826562
小兰：我猜7826562
小红：恭喜你，你猜对了
小红：你真厉害，只用了27次！
小兰：小意思！

四、思考总结

1、二分法的本质

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

2、注意

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

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2022-0-19，如有侵权请联系 cloudcommunity@tencent 删除前往查看minsystem测试算法max