Missing numbers from 0 to n-1 (simple difficulty)

Title Overview ( Simple difficulty )

Ideas and code

Train of thought display

Sort the search problem in the array , think first of Dichotomy solve .
I didn't expect this topic to use dichotomy , Let's go directly to the code , It seems that I have done less

Code example

class Solution {
    
    public int missingNumber(int[] nums) {
    
       int i =0,j = nums.length - 1;
 
       while(i <= j) {
    
           int mid = (i+j)/2;
           if(nums[mid] == mid) {
    
              i= mid+1;
           }else {
    
              j = mid-1;
           }
       }
       return i;
    }
}

matters needing attention

1： Let's first look at the core idea

           if(nums[mid] == mid) {
    
              i= mid+1;
           }else {
    
              j = mid-1;
           }

Because we have a length of n-1 Incremental sort array of , And every number is in the range 0～n-1 within , The meaning of this sentence is equivalent to that the value of the array subscript is equal to the value stored in the array , for example ：nums[0]=0,nums[1]=1…
So when nums[mid] = mid When , It means that the numbers leading up to the subscript in our middle are the same as those of its subscript , Without us nums[mid] It can't be equal to mid Of , Then the missing numbers in our array can only be found in our mid After subscript , So we can discard half of the data every time , Every time it goes down 1/2 The scale of , Similar to a binary tree , The number of searches is the height of the binary tree , Therefore, the complexity is reduced to log2N --> O(logN). So let i=mid+1, contrary , If nums[mid] != mid, Explain that the number that is less can only be in our mid Before subscribing , At this point, we need j = mid-1
2:
Now our while In circulation i Yes, we must Less than or equal to j Of ：
If it's less than j Words , At this time, the following test cases will fail ：