Topic describes

Their thinking

  • The idea of dichotomy is adopted in this question
  • The key is to use binary search to find the relationship between the subscript of the median and the element value

The problem solving code

var missingNumber = function(nums) {
    / /! The question uses the idea of dichotomy
    // Define the left pointer
    let left = 0;
    // Define the right pointer
    let right = nums.length - 1;
    if(nums[right] ! == nums.length)return nums.length;
    if (nums[0]! = =0) return 0;
    // enter the loop
    while (left < right) {
        // Find the subscript of the median
        let mid = Math.floor((left + right) / 2);
        if (nums[mid] === mid) {
            // If the median subscript is the same as the element value, the missing value is to the right of the median
            // Move the left pointer to the right of the median
            left = mid + 1
        } else if (nums[mid] > mid) {
            // Indicate that the missing is to the left of the medianright = mid; }}return left;
};
Copy the code

Conclusion (this topic gives us the enlightenment of thinking)

  • Lesson 1: Learn to use binary search