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

类似蠡口妖灵遛凌， 只是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. }

复制代码