{"id":11412,"date":"2022-02-23T02:29:39","date_gmt":"2022-02-23T02:29:39","guid":{"rendered":"https:\/\/www.softwareeverydayblog.com\/?p=11412"},"modified":"2022-02-23T02:31:35","modified_gmt":"2022-02-23T02:31:35","slug":"programming-problem-find-minimum-in-rotated-sorted-array-ii","status":"publish","type":"post","link":"https:\/\/www.softwareeverydayblog.com\/?p=11412","title":{"rendered":"[Programming Problem] Find Minimum in Rotated Sorted Array II"},"content":{"rendered":"<p>Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,4,4,5,6,7] might become:<\/p>\n<ul>\n<li>[4,5,6,7,0,1,4] if it was rotated 4 times.<\/li>\n<li>[0,1,4,4,5,6,7] if it was rotated 7 times.<\/li>\n<\/ul>\n<p>Notice that rotating an array [a[0], a[1], a[2], &#8230;, a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], &#8230;, a[n-2]].<\/p>\n<p>Given the sorted rotated array nums that may contain duplicates, return the minimum element of this array.<\/p>\n<p>You must decrease the overall operation steps as much as possible.<\/p>\n<p><strong>Example 1:<\/strong><br \/>\nInput: nums = [1,3,5]<br \/>\nOutput: 1<\/p>\n<p><strong>Example 2:<\/strong><br \/>\nInput: nums = [2,2,2,0,1]<br \/>\nOutput: 0<\/p>\n<p>[<a href=\"https:\/\/leetcode.com\/problems\/find-minimum-in-rotated-sorted-array-ii\/\" rel=\"noopener\" target=\"_blank\">Problem Link<\/a>]<\/p>\n<p>We use a `modified` binary search to find the minimum element:-<\/p>\n<ul>\n<li>At every point, compare (&#8216;i&#8217;, &#8216;mid&#8217;) with (&#8216;mid+1&#8217;, &#8216;j&#8217;). Whichever section has the lower value, let&#8217;s move that direction. Because of duplicates, we might be in a situation where there&#8217;s no one clear winner. In that case, move in both directions.\n<pre lang=\"javascript\">\r\nif ( (a < c &#038;&#038; a < d) || (b < c &#038;&#038; b < d) ) \/\/ go left\r\nelse if ((c > a && c > b) || (d > a && d > b)) \/\/ go right\r\nelse \/\/ go both directions.\r\n<\/pre>\n<\/li>\n<li>Return the last number remaining in the recursion (when i === j)<\/li>\n<\/ul>\n<pre lang=\"javascript\">\r\n\/**\r\n * @param {number[]} nums\r\n * @return {number}\r\n *\/\r\nvar findMin = function(nums) {\r\n    return findMinRecursive(nums, 0, nums.length-1);\r\n};\r\n\r\nvar findMinRecursive = function(nums, i, j) {    \r\n    if (i === j) return nums[i];\r\n    \r\n    let mid = i + Math.floor((j-i)\/2);\r\n    const a = nums[i];\r\n    const b = nums[mid];\r\n    const c = nums[mid + 1];\r\n    const d = nums[j];\r\n    \r\n    let left = Number.MAX_VALUE;\r\n    let right = Number.MAX_VALUE;\r\n    if ((a < c &#038;&#038; a < d) || (b < c &#038;&#038; b < d)) {\r\n        \/\/ go left\r\n        left = findMinRecursive(nums, i, mid);\r\n    } else if ((c > a && c > b) || (d > a && d > b)) {\r\n        right = findMinRecursive(nums, mid+1, j);\r\n    } else {\r\n        \/\/ go both\r\n        left = findMinRecursive(nums, i, mid);\r\n        right = findMinRecursive(nums, mid+1, j);\r\n    }\r\n    \r\n    return Math.min(left, right);\r\n};\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,4,4,5,6,7] might become: [4,5,6,7,0,1,4] if it was rotated 4 times. [0,1,4,4,5,6,7] if it was rotated 7 times. Notice that rotating an array [a[0], a[1], a[2], &#8230;, a[n-1]] 1 time results in the [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-11412","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts\/11412","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=11412"}],"version-history":[{"count":3,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts\/11412\/revisions"}],"predecessor-version":[{"id":11414,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts\/11412\/revisions\/11414"}],"wp:attachment":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=11412"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=11412"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=11412"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}