Today I would like to share with you the next LeetCode medium difficulty problem [search for rotation sort array II](leetcode-cn.com/problems/co…)

Here is mainly to share ideas and comments, for you to better understand the problem solution, the code part is to refer to LeetCode translated into javascript code,

The title

An array of integers, nums, is known to exist in non-descending order, and the values in the array need not be different from each other.

Before being passed to the function, nums is rotated on some previously unknown subscript k (0 <= k < nums.length), Make the array [nums [k], nums [k + 1),…, nums] [n – 1, nums [0], nums [1],…, nums [k – 1]] (subscript starting from 0). ,1,2,4,4,4,5,6,6,7 [0], for example, in the subscript 5 after rotation may become,5,6,6,7,0,1,2,4,4 [4].

Given your rotated array nums and an integer target, write a function to determine whether the given target value exists in the array. Return true if the target value exists in NUMs, false otherwise.

Example 1: Input: nums = [2,5,6,0,0,1,2], target = 0 Output: true Example 2: Input: nums = [2,5,6,0,0,1,2], target = 3 Output: falseCopy the code

Analysis of the

1. If there are duplicate values, nums[L]=== NUMs [mid] exists

2. Part of the array is ascending and part of the array is unordered. Determine whether the target is in an ordered array and narrow the range

Return true if nums[mid]===target

solution

* Binary search + deduplicate

* /

Solution 1: binary search + deduplicate method *

Train of thought1.Let's get rid of the repetitive distractions2.Reduce the spacevar search = function (nums, target) {
  let l = 0;
  let r = nums.length - 1;

  while (l <= r) {
    const mid = Math.floor(l + (r - l) / 2);

    // Check whether mid is a target to prepare for the following lookup
    if (nums[mid] === target) {
      return true;
    }

    Nums [mid] = nums[mid] = nums[mid] = nums[mid] = nums[mid
    / / note that there must add l < mid or l may be greater than the mid, such as,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,1 [1]
    while (l < mid && nums[l] === nums[mid]) l++;

    // Target must be on the right side when l===mid
    if (nums[l] <= nums[mid]) {
      // If target is in an ordered sequence,
      if (nums[l] <= target && target < nums[mid]) {
        // This must be r=mid or you will miss the answer
        r = mid - 1;
      } else {
        l = mid + 1; }}else {
      // The right hand side is the ordered sequence

      If target is in an ordered sequence,
      if (nums[mid] < target && target <= nums[r]) {
        // This must be r=mid or you will miss the answer
        l = mid + 1;
      } else {
        r = mid - 1; }}}// Return false if it is not found
  return false;
};

/* Complexity time O(logn) space O(1) */
Copy the code

conclusion

So this problem, again, is looking at your understanding of binary search, of rotating arrays, and there’s a lot of repetition in there, so there’s a lot more to think about, a lot more constraints to think about in order to do binary search, and if you practice a lot and understand a lot, you’ll get the hang of it.

You can look at a column I share (front-end algorithm) there are more questions about the algorithm to share, I hope to help you, I will try to keep updated every night, if you like the trouble to help me a like, thank you very much

The purpose of this article is to study, discuss and share the experience in the process of learning algorithm. Part of the material in this article comes from the network. If there is infringement, please contact delete, [email protected]