【面试新题】绝妙的二分查找题，一定要练习一下

刚看到一道二分查找面试真题，题型和所用的模版和已有的二分题模版都不同，有那么一点quick select的意思又有些不同。鉴于二分查找本是面试官最爱问的题，但原题数目有限，时间久了，人人都做熟了，就不再问了。若市面上出个新马甲，可能会被问一段时间。建议刚写过十来道二分原题的新手试试这道题。

您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

加一个简短的，大家更熟悉的非递归实现：

您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

发个java的，请指点

1. public int findKthMissing(int[] nums, int k) {
   
2.         if (nums == null || nums.length < 2) {
   
3.                 return -1;
   
4.         }
   
5.         int left = 0;
   
6.         int right = nums.length - 1;
   
7.         while (left + 1 < right) {
   
8.                 int mid = left + (right - left) / 2;
   
9.                 int all = (nums[mid] - nums[left] + 1) - (mid - left + 1);
   
10.                 if (k > all) {
    
11.                         k -= all;
    
12.                         left = mid;
    
13.                 } else {
    
14.                         right = mid;
    
15.                 }
    
16.         }
    
17.         if (nums[left] + k >= nums[right]) {
    
18.                 return -1;
    
19.         } else {
    
20.                 return nums[left] + k;
    
21.         }
    
22.     }

复制代码

补充内容 (2019-5-17 12:42):
不太会用加代码== 所以就成这个版面了==

补充内容 (2019-5-17 12:43):
又显示出来啦 尴尬

回应地里新农，重贴降低隐藏积分限制。

您好！
本帖隐藏的内容需要积分高于 120 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 120 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

本文被选为全站置顶文章之一。
作者获得大米奖励。谢谢你的分享。

贴代码的同学，都获得了大米奖励。

C++ version

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

补充内容 (2019-5-18 06:24):
输出
3
5
6
7
8
12
13
14
-1
-1
-1
-1
-1
-1
-1
-1

哎，要提升看python的能力了，java刷习惯了，看python好生不习惯。。。但看了半天终于看懂了！
我觉得 `return nums[end] - nums[start] - (end - start)` 这一步挺妙的，当场提示我用二分法的话，我若想不到这一步，还是解不出来。回去后我补个java版本的解法。谢谢楼主分享

tinlittle 发表于 2019-5-16 13:28
加一个简短的，大家更熟悉的非递归实现：
**** 本内容被作者隐藏 ****

感谢分享！我有一个问题，这个非递归的方法。对于while循环的终止条件，为什么start + 1 != end 呢？

小狗雪碧 发表于 2019-5-16 11:59
感谢分享！我有一个问题，这个非递归的方法。对于while循环的终止条件，为什么start + 1 != end 呢？

因为是要找一个range呀，漏掉的数一定是在给出的两个数之间。你要是用start<=end就不对了。

也许你是问为什么不是start+1 < end？那个也对。这个是个人习惯，start+1 != end 逻辑上更精确。要纠结的话，推荐用start+1 < end，这个更好记，遇到极端初始条件不容易错。

赞一个，感觉核心就是能在O（1）时间内得出数组中两个index间miss了多少number，这样就可以用平常的二分法O（logn）求解了

tinlittle 发表于 2019-5-17 03:51
因为是要找一个range呀，漏掉的数一定是在给出的两个数之间。你要是用start

太感谢了！“漏掉的数字一定是在给出的两个数字之间”  这句话点醒了我！！！ 楼主以后要多发刷题笔记啊！

这个题在地里的面经经常出现，我大概看过三次吧。
随手找到其中一个：http://www.1point3acres.com/bbs/ ... sortid%3D311%26sear
choption%5B3089%5D%5Bvalue%5D%5B3%5D%3D3%26searchoption%5B3089%5D%5Btype%5D%3Dcheckbox%26searchoption%5B3046
%5D%5Bvalue%5D%3D1%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311

补充内容 (2019-5-17 09:20):
不好意思，这个链接贴出来的时候broken了。。。
这个可以用：https://www.1point3acres.com/bbs ... read&tid=443454

zbh9000510 发表于 2019-5-16 15:01
哎，要提升看python的能力了，java刷习惯了，看python好生不习惯。。。但看了半天终于看懂了！
我觉得 `re ...

好啊，欢迎补充Java版，传上来给你加米。

wisdompeak2 发表于 2019-5-16 18:13
这个题在地里的面经经常出现，我大概看过三次吧。
随手找到其中一个：http://www.1point3acres.com/bbs/fo ...

老哥眼力和记性都强。搜索引擎是比不上人民雪亮的眼睛啊。