{"id":11404,"date":"2022-02-22T22:41:28","date_gmt":"2022-02-22T22:41:28","guid":{"rendered":"https:\/\/www.softwareeverydayblog.com\/?p=11404"},"modified":"2022-02-23T02:26:47","modified_gmt":"2022-02-23T02:26:47","slug":"programming-problem-find-minimum-in-rotated-sorted-array","status":"publish","type":"post","link":"https:\/\/www.softwareeverydayblog.com\/?p=11404","title":{"rendered":"[Programming Problem] Find Minimum in Rotated Sorted Array"},"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,2,4,5,6,7] might become:<\/p>\n<ul>\n<li>[4,5,6,7,0,1,2] if it was rotated 4 times.<\/li>\n<li>[0,1,2,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 of unique elements, return the minimum element of this array.<\/p>\n<p>You must write an algorithm that runs in O(log n) time.<\/p>\n<p><strong>Example 1:<\/strong><br \/>\nInput: nums = [3,4,5,1,2]<br \/>\nOutput: 1<br \/>\nExplanation: The original array was [1,2,3,4,5] rotated 3 times.<\/p>\n<p><strong>Example 2:<\/strong><br \/>\nInput: nums = [4,5,6,7,0,1,2]<br \/>\nOutput: 0<br \/>\nExplanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.<\/p>\n<p><strong>Example 3:<\/strong><br \/>\nInput: nums = [11,13,15,17]<br \/>\nOutput: 11<br \/>\nExplanation: The original array was [11,13,15,17] and it was rotated 4 times. <\/p>\n<p>[<a href=\"https:\/\/leetcode.com\/problems\/find-minimum-in-rotated-sorted-array\/\" 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.\n<pre lang=\"javascript\">\r\nif ( (a < c &#038;&#038; a < d) || (b < c &#038;&#038; b < d) ) \/\/ go left\r\nelse \/\/ go right\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        \r\n    \/\/ one or two digits\r\n    if ( i === j ) return nums[i];\r\n    \r\n    let mid = i + Math.floor((j-i)\/2);\r\n    let a = nums[i];\r\n    let b = nums[mid];\r\n    let c = nums[mid+1];\r\n    let d = nums[j];\r\n    \r\n    if ( (a < c &#038;&#038; a < d) || (b < c &#038;&#038; b < d) ) {\r\n        \/\/ go left\r\n        return findMinRecursive(nums, i, mid);\r\n    } else {\r\n        \/\/ go right\r\n        return findMinRecursive(nums, mid+1, j);\r\n    }\r\n    \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,2,4,5,6,7] might become: [4,5,6,7,0,1,2] if it was rotated 4 times. [0,1,2,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-11404","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts\/11404","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=11404"}],"version-history":[{"count":5,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts\/11404\/revisions"}],"predecessor-version":[{"id":11408,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts\/11404\/revisions\/11408"}],"wp:attachment":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=11404"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=11404"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=11404"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}