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

liaohs49 发表于 2019-5-18 20:38
Java version, 送一个unittest
[mw_shl_code=java,true]import static org.junit.Assert.*;

You are given a sorted without any duplicate integer array

test case 要改改

补充内容 (2019-5-20 01:42):
my fault, never mind

挺好的写的

这一题是cyclic sort 的变种

liaohs49 发表于 2019-5-18 20:38
Java version, 送一个unittest
[mw_shl_code=java,true]import static org.junit.Assert.*;

有点typo 无视无视

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

求教大神一般怎么搜“想要”的面经呀？求经验!

zbh9000510 发表于 2019-5-20 21:26
求教大神一般怎么搜“想要”的面经呀？求经验!

上面的免米搜索可以搜啊。

Tina_Qity 发表于 2019-5-17 12:41
发个java的，请指点
[mw_shl_code=java,true]public int findKthMissing(int[] nums, int k) {
        i ...

多谢分享，

我总结了一下这个代码的思路，各位大神可以指点。

  思路， 二分查找：
  1. 先表明每个数组里面数字的下标[2（0）,4（1）,7（2）,8（3）,9（4）,15（5）]。
  2. 因为数组是排过序的，所以任意两个数字之差 + 1 就代表了这两个数字中间应该有多少个数字。比如原数组中 2 到 7 之间有6个数。
     这些数字分别是 [2, 3, 4, 5, 6, 7]， 正好是 7 - 2 + 1 = 6。
  3. 因为数组是排过序的，所以任何两个数的下标之差 + 1 就代表了这个两个数字中间实际有多少个数字。 比如原数组中 2（0） 到 7 （2） 之间有3个数。
     这些数字分别是 [2（0）,4（1）,7（2）]， 正好是2 - 0 + 1 = 4。
  4. 我们分别可以求到两个数中应该有多少个数字nums[j] - nums + 1, 和两个数中实际有多少个数字j - i + 1, 用应该有的数字个数-实际有的
      数字个数 = 虚拟数组个数（virtual), 这样我们就能慢慢找到第k个数。
  5. 在二分查找时，我们有left变量指向数组最左边，和right变量指向数组最右边，和middle变量指向数组中间。 我们最开始假设left和right下标中间一定
      有大于等于k个虚拟数组，然后慢慢缩小查找范围到第k个虚拟数。
  6. 如果我们先求left和middle的虚拟数组个数 virtual = (nums[middle] - nums[left] + 1) - (middle - left + 1)
  7. 如果virtual小于k，表示我们找到了过少的虚拟数组，找打了前virtual个数， 然后继续向右二分搜索剩下的virtual -= k， left = middle，virtual -= k
  8. 如果virtual大于k，表示我们找到了太多的虚拟数组，需要缩小搜索范围，right = middle， 完成二分搜索

wangbd 发表于 2019-5-21 04:38
多谢分享，

我总结了一下这个代码的思路，各位大神可以指点。

讲的挺好的，我有两个问题，不知道能否帮我解答下
1：left + 1 < right为什么要这样？
2：什么情况下会有“if (nums[left] + k >= nums[right]) ”这种情况呢？谢谢

还有一个typo：正好是2 - 0 + 1 = 4。应该是3.

谢谢楼主！已加米～

路飞之父 发表于 2019-5-21 11:14
讲的挺好的，我有两个问题，不知道能否帮我解答下
1：left + 1 < right为什么要这样？
2：什么情况下会 ...

1. 这样是因为我们可以保证在while循环结束的时候，left和right指针永远只有2种状态，相交或相邻。这样方便最后的if语句判断。

2. 当你的right指针移出初始位置之后，就可能发生你这种情况。比如说给数组
[2,4,7,8,9,15]
left   = 0
right = 5
k      = 1

我们就会到上述条件【8】，然后直到while 结束。

谢谢你的typo检查，我看看怎么把这几个错别字改过来。