[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

286 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

  69. I must get across my respect for your kindness supporting individuals who absolutely need guidance on this important topic. Your personal commitment to passing the message throughout came to be definitely valuable and have frequently allowed some individuals just like me to attain their endeavors. This important recommendations means a whole lot a person like me and a whole lot more to my peers. Warm regards; from everyone of us.

    Reply

  70. I must show thanks to the writer just for rescuing me from this particular dilemma. Just after browsing through the the net and coming across techniques which were not powerful, I figured my life was over. Living devoid of the solutions to the difficulties you’ve sorted out by means of your guideline is a critical case, as well as the ones that could have badly affected my entire career if I had not discovered your site. Your personal skills and kindness in controlling almost everything was helpful. I’m not sure what I would’ve done if I had not come across such a thing like this. I can also at this point look forward to my future. Thanks a lot very much for your impressive and sensible help. I will not hesitate to suggest your site to anyone who should get support on this subject matter.

    Reply

  77. I must point out my affection for your kindness for those people who really want help on this particular question. Your very own commitment to passing the message all around had become especially effective and has in most cases encouraged many people much like me to reach their objectives. Your important useful information implies so much to me and substantially more to my office workers. Thanks a ton; from everyone of us.

    Reply

  79. I precisely wished to appreciate you again. I am not sure what I would have sorted out in the absence of the aspects shared by you relating to my subject matter. This has been the challenging dilemma in my circumstances, nevertheless discovering a new professional fashion you solved it forced me to leap with fulfillment. I will be happy for this service and in addition expect you recognize what an amazing job you were providing training other individuals by way of a blog. More than likely you haven’t met all of us.

    Reply

  84. I have to convey my passion for your kindness for individuals that require help on this important concern. Your special commitment to getting the solution across had become certainly interesting and has usually enabled men and women like me to get to their aims. This useful suggestions indicates a great deal a person like me and additionally to my colleagues. Thank you; from all of us.

    Reply

  105. I precisely desired to appreciate you all over again. I do not know the things that I might have accomplished in the absence of those ideas discussed by you directly on such problem. It had been the daunting issue in my circumstances, but taking note of your skilled technique you dealt with that took me to cry for fulfillment. I’m grateful for this advice and in addition hope that you are aware of an amazing job you have been putting in educating the rest thru your website. Most probably you’ve never met any of us.

    Reply

  137. Needed to create you that very little observation to finally give thanks yet again relating to the stunning techniques you’ve discussed in this case. It has been really pretty generous with people like you giving openly exactly what most people might have marketed as an e-book to earn some bucks on their own, primarily seeing that you could possibly have tried it if you desired. Those basics also served to be the easy way to be certain that most people have the same eagerness really like my own to grasp whole lot more concerning this issue. I’m certain there are several more pleasurable sessions up front for those who check out your site.

    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