[Programming Problem] Find Minimum in Rotated Sorted Array

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], …, a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], …, a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

Example 1:
Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2:
Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3:
Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times.

[Problem Link]

We use a `modified` binary search to find the minimum element:-

  • At every point, compare (‘i’, ‘mid’) with (‘mid+1’, ‘j’). Whichever section has the lower value, let’s move that direction. 
    if ( (a < c && a < d) || (b < c && b < d) ) // go left
else // go right
  • Return the last number remaining in the recursion (when i === j)
/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
    return findMinRecursive(nums, 0, nums.length-1)
};
 
var findMinRecursive = function(nums, i, j) {
 
    // one or two digits
    if ( i === j ) return nums[i];
 
    let mid = i + Math.floor((j-i)/2);
    let a = nums[i];
    let b = nums[mid];
    let c = nums[mid+1];
    let d = nums[j];
 
    if ( (a < c && a < d) || (b < c && b < d) ) {
        // go left
        return findMinRecursive(nums, i, mid);
    } else {
        // go right
        return findMinRecursive(nums, mid+1, j);
    }
 
}

softwareeveryday

68 thoughts on “[Programming Problem] Find Minimum in Rotated Sorted Array”

  11. My wife and i ended up being relieved that John managed to round up his studies through the ideas he discovered when using the web site. It’s not at all simplistic just to possibly be making a gift of tricks that many men and women may have been selling. And we do know we have got you to thank for this. Most of the illustrations you made, the straightforward blog menu, the friendships your site help instill – it’s got most overwhelming, and it’s really assisting our son and our family consider that the subject matter is exciting, which is certainly pretty important. Many thanks for everything!

    Reply

  13. I would like to get across my passion for your kindness supporting those people that require help with this subject. Your very own dedication to passing the solution across was surprisingly informative and has in most cases encouraged individuals like me to achieve their goals. Your amazing warm and friendly guidelines means a whole lot a person like me and somewhat more to my peers. Regards; from all of us.

    Reply

  14. Needed to put you this little bit of remark in order to give thanks the moment again for your personal fantastic techniques you’ve provided above. It was quite remarkably open-handed of people like you to allow publicly precisely what many individuals could have supplied for an e-book to make some dough for their own end, most notably considering the fact that you might well have done it in the event you considered necessary. The concepts in addition worked as a fantastic way to understand that some people have similar passion the same as my personal own to see a great deal more in respect of this condition. I know there are numerous more fun times up front for individuals who scan your site.

    Reply

  15. I precisely wished to say thanks once more. I’m not certain what I would’ve sorted out in the absence of these techniques revealed by you on this theme. It actually was a very scary issue in my view, however , coming across a expert way you processed it made me to weep over contentment. I’m just thankful for the help as well as sincerely hope you find out what an amazing job that you are accomplishing training people today using a blog. More than likely you have never encountered all of us.

    Reply

  17. Needed to write you one little bit of remark to help thank you very much over again for your wonderful tricks you’ve documented on this page. It’s certainly shockingly open-handed with people like you to provide without restraint precisely what a lot of people might have sold for an e-book to earn some profit for themselves, mostly considering the fact that you might have done it in case you considered necessary. These basics also worked to be a fantastic way to fully grasp that the rest have the identical desire really like my personal own to understand a lot more when it comes to this condition. I know there are millions of more fun times ahead for those who look over your site.

    Reply

  18. I am only writing to let you be aware of what a fine encounter my wife’s daughter had reading your site. She came to understand so many pieces, not to mention what it’s like to have a marvelous helping heart to make certain people without difficulty learn a variety of multifaceted issues. You really did more than our expected results. Thank you for distributing those beneficial, safe, explanatory and even cool thoughts on the topic to Emily.

    Reply

  19. I would like to express my gratitude for your kindness for men and women who really want assistance with this particular area. Your very own dedication to getting the solution all through appears to be remarkably good and has without exception made those much like me to attain their targets. Your personal invaluable publication means this much to me and a whole lot more to my fellow workers. With thanks; from each one of us.

    Reply

  20. I wanted to draft you one bit of word so as to say thanks a lot over again with your gorgeous tips you have featured here. It has been really extremely generous of people like you giving freely what exactly most people could possibly have made available as an e book to help with making some cash for their own end, most importantly considering the fact that you could have tried it if you ever desired. The creative ideas as well worked as the fantastic way to realize that many people have the same dream the same as my very own to realize much more when it comes to this problem. I’m certain there are numerous more fun instances in the future for those who discover your website.

    Reply

  21. I have to point out my passion for your kind-heartedness for persons who need help with this important content. Your personal commitment to getting the solution all over ended up being wonderfully practical and has continually helped somebody much like me to reach their dreams. Your warm and friendly guideline means so much a person like me and far more to my office colleagues. Thank you; from each one of us.

    Reply

  22. I would like to voice my appreciation for your kindness for those people that really need guidance on this question. Your special commitment to passing the solution all-around has been astonishingly significant and have in most cases empowered those just like me to arrive at their desired goals. Your new warm and helpful guideline indicates so much to me and a whole lot more to my mates. Best wishes; from all of us.

    Reply

  23. I must express my thanks to you for rescuing me from this particular condition. Right after looking out throughout the the net and meeting tricks that were not helpful, I believed my life was gone. Being alive devoid of the solutions to the problems you’ve solved through your main short article is a critical case, as well as the kind that could have badly damaged my entire career if I hadn’t encountered your site. Your own personal knowledge and kindness in taking care of every part was excellent. I am not sure what I would’ve done if I had not come across such a thing like this. I can also at this time look ahead to my future. Thank you so much for this professional and sensible guide. I will not hesitate to suggest the blog to any individual who needs and wants tips about this issue.

    Reply

  24. I not to mention my pals ended up taking note of the best helpful tips located on your site and so then developed an awful suspicion I never thanked you for those techniques. These men are already consequently passionate to see all of them and already have truly been tapping into these things. Appreciate your getting considerably considerate and then for considering such brilliant topics millions of individuals are really eager to be aware of. My personal sincere apologies for not expressing appreciation to you sooner.

    Reply

  25. I am writing to make you know of the fabulous experience our child undergone using the blog. She learned too many things, which include how it is like to have a very effective teaching character to make the others completely comprehend a number of multifaceted subject matter. You actually exceeded my expected results. Many thanks for producing the warm and friendly, healthy, explanatory and unique tips about the topic to Ethel.

    Reply

  59. I’m writing to make you be aware of of the incredible discovery my friend’s daughter developed browsing your site. She realized so many things, which include what it’s like to have a great giving character to get most people easily know just exactly specified tricky topics. You undoubtedly did more than visitors’ desires. Thanks for presenting such practical, trustworthy, educational not to mention unique tips on that topic to Evelyn.

    Reply

  65. I wish to get across my appreciation for your kind-heartedness in support of persons that must have assistance with your matter. Your real dedication to passing the solution across has been wonderfully insightful and have consistently empowered ladies like me to realize their aims. Your personal important useful information indicates so much to me and even further to my office workers. Regards; from everyone of us.

    Reply

  68. I am glad for writing to make you understand of the terrific experience my friend’s child had going through your site. She noticed so many issues, with the inclusion of what it’s like to have an ideal giving mindset to make the others smoothly comprehend certain hard to do subject areas. You truly did more than visitors’ expectations. Many thanks for displaying these interesting, safe, educational and fun tips on the topic to Tanya.

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *

[Programming Problem] Subsets II
Read More
[Programming Problem] Flatten Binary Tree to Linked List
Read More
[Programming Problem] Largest Number
Read More