三类二分题型的第二类——在某个范围内寻找一个整数 ｜Java 刷题打卡

本文正在参加「Java主题月 – Java 刷题打卡」，详情查看 活动链接

这类题最简单的应用就是猜数字了（既然是最简单，我就简单介绍下，然后看稍微有点难度的题）

1-100猜一个数字，猜大了告诉你大了，猜小了告诉你小了，小的时候大家应该都玩过。

一、题目描述：

重要的是这道题还有进阶：

进阶：

• 如何证明 nums 中至少存在一个重复的数字?
• 你可以在不修改数组 nums 的情况下解决这个问题吗？
• 你可以只用常量级 O(1) 的额外空间解决这个问题吗？
• 你可以设计一个时间复杂度小于 O(n2) 的解决方案吗？

二、思路分析：

这里就不讨论非进阶的解法了，

为了防止有人觉得“你这先知道用什么算法，后写代码，不就是按图索骥嘛”（事实上我学习时也总有这类苦恼），这里说些“应试技巧”

1. 首先，我们都知道：时间，空间总要有取舍。（除非是数学方法）
2. 其次，限制空间O(1)的情况下，就很难让时间复杂度O(logn)或者O(n)了
3. 代码限制了n^2的时间复杂度，那么最简单的方式就是优化至nlogn

怎么优化？

先脑子里想出一个n^2的算法（你肯定想出来了），那么遍历i和遍历j，那部分比较好优化呢？

• 遍历j是在和i相同的数，那就很难优化，因为总要一个个比对，
• 遍历i是在寻找答案（因为当你退出循环的时候，i一定是你的答案），如果优化的话就需要保证一个升序的关系，这样才好用二分进行优化。

可答案也没给我们升序啊？

这就是这类题和二分联系到一起的着力点了，抬头看下标题“在某个范围内寻找一个整数”，某个范围本身隐式的表达了自己的顺序性，但具体怎么隐需要具体分析：

再说说猜数字：

猜数字的题中给了你每次猜的结果，换句话说，如果arr[mid] != target时，你是知道该选择[left，mid – 1] 还是 [mid + 1， right]的。

回到本题：

你需要一个方法可以判断，当mid不是答案的时候，应该选择哪个区间。

既然数组中数字范围是一定的，换句话说当arr[i] == tmp 时，如果target > tmp ，则有 tmp – 1 个元素小于tmp ， 反之则有tmp个元素小于tmp

那退出循环的条件是，只有一个元素的时候，这个元素必是target。

三、AC 代码：

//就不写其他部分了，只写个核心代码

while(left < right){
    mid = (left + right) / 2;
    int num = 0;
    for(循环计数){}
    if(num == mid - 1){
        // 说明target在[mid ， right]之间
        // 注意我用的都是闭区间
    }else if(num == mid){
        //说明target在[left ， mid)之间
    }//不会出现别的else了，老规矩，写elseif只是为了你方便
}
复制代码

四、总结：

总结下这类题型，首先你得通过“某个范围内寻找一个整数 ”来联想到二分，就像负雪大佬说的那样，算法等于模板加想法，你不背模板，入不了门，没有想法，就不会用模板。

其次是根据题中条件，找出这类范围隐藏的顺序性。

当你想到二分是根据什么分的时候，你这个问题基本也就解决了