# [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.

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); }   }```

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

1. 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!

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.

7. 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.

8. 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.

9. 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.

10. 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.

12. 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.

13. 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.

14. Donaldmog says:

can i purchase cheap nexium pills
What side effects can this medication cause? Comprehensive side effect and adverse reaction information.

15. Jamesinfam says:

Definitive journal of drugs and therapeutics. Everything information about medication.
Get warning information here. safe and effective drugs are available.

16. WillieSog says:

Medscape Drugs & Diseases. safe and effective drugs are available.
https://nexium.top/# get cheap nexium without a prescription

17. PhilipAmags says:

https://edonlinefast.com cheap ed drugs
Cautions. Drug information.

18. Efrendiome says:

drug information and news for professionals and consumers. Get here.
best ed pills online

19. RobertTak says:

Get here. Comprehensive side effect and adverse reaction information.
ed pills for sale
Everything information about medication. All trends of medicament.

20. MortonWit says:

All trends of medicament. Get here.
All trends of medicament. Get here.

21. PhilipAmags says:

Commonly Used Drugs Charts. Some trends of drugs.
pills for ed
All trends of medicament. Definitive journal of drugs and therapeutics.

22. MortonWit says:

drug information and news for professionals and consumers. Drugs information sheet.
https://edonlinefast.com cheap ed pills
Everything information about medication. Top 100 Searched Drugs.

23. RobertTak says:

What side effects can this medication cause? Actual trends of drug.
https://edonlinefast.com cure ed
Prescription Drug Information, Interactions & Side. Drugs information sheet.

24. PhilipAmags says:

Prescription Drug Information, Interactions & Side. Actual trends of drug.
best ed drugs
Get warning information here. Best and news about drug.

25. Jeffreyjag says:

п»їMedicament prescribing information. Everything what you want to know about pills.
Drugs information sheet. Comprehensive side effect and adverse reaction information.

26. EdgarHOr says:

Some are medicines that help people when doctors prescribe. Generic Name.
Actual trends of drug. Prescription Drug Information, Interactions & Side.

27. Jeffreyjag says:

Everything what you want to know about pills. What side effects can this medication cause?
https://canadianfast.online/# how to get prescription drugs without doctor
Learn about the side effects, dosages, and interactions. Generic Name.

28. EdgarHOr says:

earch our drug database. Actual trends of drug.
prescription drugs
drug information and news for professionals and consumers. Drugs information sheet.

29. VictorSpast says:

п»їMedicament prescribing information. earch our drug database.
https://canadianfast.com/# prescription drugs online without doctor
Some trends of drugs. drug information and news for professionals and consumers.

30. 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.

31. 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.

32. 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.