Topic describes

Serialization (serialization)

  • When I first looked at this problem, I realized that if I find the first element smaller than the first element in the array, I should return the first element
  • Look at the answer key, by adopting the idea of a binary search, the first pointer to the first element, second pointer to the last element, digit is greater than the most the right side of the element, target elements are still on the right side of the median, our target element is the smallest that value, at this time to left = mid + 1, if the median is less than the right elements, So the median might be the target element, so let’s say right = mid; If the median is equal to the rightmost element, say right–;
  • At the end of the loop, the element corresponding to the left subscript should be the smallest element.

Serialization code

var minArray = function(numbers) {
    let left = 0;
    let right = numbers.length - 1;
    / /! Our goal: make the left and right Pointers point to the smallest element, and then terminate the loop
    while (left < right) {
        const mid = left + right >>> 1;
        if (numbers[mid] > numbers[right]) {
            // If the median is larger than the rightmost, the target element is still to the right of the median
            left = mid + 1;
        } else if (numbers[mid] < numbers[right]) {
            // If the median is smaller than the rightmost one
            right = mid;
        } else{ right--; }}return numbers[left];
};
Copy the code

Conclusion (this topic gives us the enlightenment of thinking)

  • Lesson 1: Learn to find the median using the zero-fill shift 1 bit to the right
  • Lesson 2: Learn to use the idea of binary search to find minimums