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

感谢楼主分享，非常好的一道题。我想了一下，这个题是不是可以反过来问，给定一个number，给出它在missing的序列里排第几，比如输入一个5，返回2
下面是我的解法：

1.         static int KthMissNumber(int[] nums, int value)
   
2.         {
   
3.             int left = 0, right = nums.Length;
   
4.             while (left < right)
   
5.             {
   
6.                 int mid = (left + right) / 2;
   
7.                 if (nums[mid] > value)
   
8.                 {
   
9.                     right = mid;
   
10.                 }
    
11.                 else if (nums[mid] < value)
    
12.                 {
    
13.                     left = mid + 1;
    
14.                 }
    
15.                 else
    
16.                 {
    
17.                     return mid;
    
18.                 }
    
19.             }
    
20. 
    
21.             if (nums[left] < value)
    
22.             {
    
23.                 return nums[left] - nums[0] - left + 1;
    
24.             }
    
25.             else
    
26.             {
    
27.                 return nums[left-1] - nums[0] - left + 2;
    
28.             }
    
29.         }
    
30.     }

复制代码

补充内容 (2019-5-24 01:49):
这里有个假设是value一定是missing number，所以return mid;那一行永远不会执行

1. // Basic Ideas: binary search
   
2. // Complexity: Time O(log(n)), Space O(1)
   
3. func missingElement(nums []int, k int) int {
   
4.     totalMiss := (nums[len(nums)-1]-nums[0]+1)-len(nums)
   
5.     if totalMiss < k {
   
6.         return nums[len(nums)-1]+k-totalMiss
   
7.     }
   
8.     left, right := 0, len(nums)-1
   
9.     for left+1<right {
   
10.         mid := (right-left)/2+left
    
11.         cnt := (nums[mid]-nums[left])-(mid-left)
    
12.         if cnt >= k {
    
13.             // search left part
    
14.             right = mid
    
15.         } else {
    
16.             // search right part
    
17.             left = mid
    
18.             k -= cnt
    
19.         }
    
20.     }
    
21.     // left.right
    
22.     return nums[left]+k
    
23. }

复制代码

类似蠡口妖灵遛凌， 只是missing的不会超过原数组的最大值

My solution in C++

1. // number of missing integers in range nums[start, end]
   
2. int numMissing(vector<int>& nums, int start, int end) {
   
3.   return (nums[end]-nums[start]) - (end - start);
   
4. }
   
5. 
   
6. int getKthMissing(vector<int>& nums, int k) {
   
7.   int n = nums.size();
   
8.   
   
9.   // validate k
   
10.   if (k <= 0 || numMissing(nums, 0, n-1) < k) return INT_MIN;
    
11.   
    
12.   int L = 0, R = n-1;
    
13.   while (R-L > 1) {
    
14.     int mid = (L+R)/2;
    
15.     int missing = numMissing(nums, L, mid);
    
16.     if (missing >= k) R = mid;
    
17.     else {
    
18.       L = mid;
    
19.       k -= missing;
    
20.     }
    
21.   }
    
22.   
    
23.   return nums[L] + k;
    
24. }

复制代码