Find Minimum in Rotated Sorted Array - Binary Search - Leetcode 153 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Twitter: / neetcode1
Discord: / discord
⭐ BLIND-75 SPREADSHEET: docs.google.com/spreadsheets/...
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
💡 BINARY SEARCH PLAYLIST: • Binary Search
Problem Link: neetcode.io/problems/find-min...
0:00 - Read the problem
1:34 - Drawing Explanation
10:10 - Coding Explanation
leetcode 153
This question was identified as a facebook interview question from here: github.com/xizhengszhang/Leet...
#rotated #array #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[@NeetCode]

🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤

[@world11191]

I've watched this video probably 10-15 times over different days, and only now is it starting to make sense. Bless.

[@regnam503]

In all fairness, this particular explanation is not the most intuitive. Still grateful tho.

[@luiggymacias5735]

if you dont know what binary search is, i would recommend to learn that first, the problem becomes more easy to understand if you know about that, and this explanation makes more sense if you try around 40 minutes to solve it by yourself, even if you dont get to the answer, the important thing is to solve it conceptually, even if you dont get to solve it with code

[@mattk.9937]

There is a much easier solution that I came up with: class Solution: def findMin(self, nums: List[int]) -> int: p1 = 0 p2 = 1 for i in range(1, len(nums)): if nums[p1] > nums[p2]: return nums[p2] p1 += 1 p2 += 1 return nums[0] You just set two pointers to the first and second elements and then update them through each iteration. If at any point the first pointer is larger than the second, you know the second is the minimum value due to the fact that the list is sorted.

[@adonis1168]

@@mattk.9937 that's o(n) solution, problem prompts you to solve it o(logn)

[@saurabhbasak9545]

@@mattk.9937 that's a good solution but not O(log n) time

[@TheOtrama]

Dear NeetCode, Thank you so much for your videos! The quality and comprehensiveness of your explanations is incredible. For every problem I solved or struggle to solve I will instantly turn to your videos. I won't even consider other KZbinrs because I know that your explanations are the best. Thank you for this quality content!

[@camoenv3272]

Shorter code (don't need to initialize a results variable, since we know that the while loop will break when left pointer is pointing at the minimum): def findMin(self, nums: List[int]) -> int: l, r = 0, len(nums) - 1 while l < r: m = l + (r - l) // 2 if nums[m] > nums[r]: l = m + 1 else: r = m return nums[l]

[@Rob-in7vp]

thanks, this solution made more sense to me

[@christianmorabito4148]

Hey I tried this, but it doesn't work for this set of nums: nums = [12, 0, 1, 2, 3, 4, 5, 6, 9, 10, 11]

[@Grawlix99]

@@christianmorabito4148 works on my end 🤔

[@christianmorabito4148]

@@Grawlix99 Oh yes!! Sorry, I was returning m (mid variable) instead of l (low variable).

[@Grawlix99]

@@christianmorabito4148 np! 😃

[@evynsrefuge]

you can actually do if m > r search right or if m > l search right. Either one works with the case added for the already sorted array

[@evynsrefuge]

because of how the sorted array and rotation works, if the inflection point is to the left of M, L and R are always larger than M, but if the inflection point is to the right of M, L and R are always smaller than M.

[@ShubhamMishra-mz4zw]

One of the best explanation of this problem. Thank you ❤

[@hrvmhv4391]

Thank for explaining this very clearly. With a minor tweak I was able to solve following as well. 154. Find Minimum in Rotated Sorted Array II

[@lxu5148]

Curious about how you modify the code to make 154 work. Do you mind sharing the script?

[@hrvmhv4391]

@@lxu5148 I tried to add pastebin link here but keeps getting deleted. But this is what my if condition looks like if(nums[lo] == nums[mi] && nums[mi] == nums[lo]) return Math.min(findMin(nums, res, lo, mi-1), findMin(nums, res, mi+1, hi)); else if(nums[mi] >= nums[lo]) // If mid is greater then everything on left, the look on right side lo = mi + 1; else hi = mi - 1;

[@lxu5148]

@@hrvmhv4391 appreciate it! I will check it when I am with my laptop.

[@buttofthejoke]

​@@hrvmhv4391 (nums[lo] == nums[mi] && nums[mi] == nums[lo]) ? didn't get it. isn't that the same condition?

[@anaisliu6709]

After watching the solution of problem 33 I solved this problem on my own! However your solution is always the best, I could learn from it a lot!

[@Byte-ul]

Just move right to mid, instead of mid -1 and you won't need to check for min result.

[@ggmadmax]

You can skip the first if condition by doing this: Instead of comparing mid pointer with left, compare it with right (all other factors remain same). For example: [4,5,6,7,0,1,2] Iteration 1: start pointer (s) = 0 end pointer (e) = 6 mid pointer (m) = (s+e)//2 =3 here, nums[m] >= nums[e]: therefore, s=m+1 Iteration 2 s=4 e=9 m = 5 here, nums[m]

[@phantomsedge5686]

i like this

[@begenchorazgeldiyev5298]

I agree, I was thinking this too. What if they rotated it n times and it is back to its original sorted state where the leftmost element is the smallest. If we compare mid to the right, and see if mid is bigger, then go right, else go left

[@JamesBond-mq7pd]

doesn't work for [3,1,2]

[@Vagabond625]

@@JamesBond-mq7pd yeah when searching left, e has to be set to m instead of m-1

[@HonduranHunk]

Wayy more intuitive, thank you bro

[@erikm9768]

Great explanation!

[@spageen]

The way I like to think about it is we're searching for the point where the sorted array 'resets' to the minimum. If the middle is less than the leftmost value, that means the 'reset' point is somewhere on the left side. Otherwise, it's on the right side.

[@DroidHolicOfficial]

Beautiful Explanation. I used the same code for the 154. Find Minimum in Rotated Sorted Array II with just one change and it was accepted. Since in 154 problem, there are duplicates as well, I added an extra check in case all elements at start, mid and end are the same. In that case, we just decrement the end pointer by 1. Otherwise, the code remains the same. while start = nums[start]: start = mid + 1 # Otherwise, we will find the minimum on the left side else: end = mid - 1

[@rmaskaban]

Works for edge cases where min as middle and [2,1]: class Solution: def findMin(self, nums: List[int]) -> int: ans=nums[0] l,r=0,len(nums)-1 while l

[@yinglll7411]

Thank you!

[@soltomoon3620]

This is one of the first medium problems that I correctly new the intuition. LETS GOO

[@khandokarsabbir9892]

Your explanation is very good. Line no 7, condition should be if (nums[l]

[@zaeem95]

I got this too, good catch.

[@ianokay]

Is the EQUAL SIGN in "(nums[l] >= nums[m])" ONLY for the case of an input like [2,1] where l=0, m=(0+1)//2 = 0 but we randomly need to check the other index value too "just because" (outside of our actual defined rules we've outlined)... just to make sure?

[@causalinference4176]

Thx NeetCode, here is my solution: class Solution: def findMin(self, nums: List[int]) -> int: left, right = 0, len(nums)-1 while left < right: mid = (left+right) // 2 if nums[mid+1] < nums[mid]: return nums[mid+1] # left sorted if nums[mid] > nums[left]: # search on right left = mid + 1 # right sorted else: # search on left right = right - 1 return nums[0]

[@GoziePO]

Does this work for [5, 1, 2]?

[@GoziePO]

shoot i guess it does

[@yomamasofat413]

are there people who have never seen this before and just came up with the solution on the spot? Kudos man

[@fenrirgreyback101]

I was able to come up with one before seeing the solution but I spent a couple hours going through examples and noticing patterns to think of the solution. Wouldn't be able to come up with it on the spot yet, but I guess that's why we practice!

[@buttslaya]

Well, if we weren't so caught up in trying to learn/solve it with binary search we could actually just look for the minimum number with one for loop 🤷‍♂

[@rongrongmiao3018]

hmmm the condition to determine if arr[mid] is in the first sequence to be arr[mid] > = arr[start] is not enough. Counter example: [4,5,6,7,0,1,2], l = 0, r = 6, mid = 3, after first update, start = mid + 1 which is 0, we are searching in subarray[0, 1, 2]in this case arr[mid] > arr[start] still holds, but it is in the second sequence. The only reason that your solution passed is because you're updating the result all the way.

[@benmiller7520]

He explained in the video that this condition does not work on sorted lists. The reason it still passes is because he has the nums[l] < nums[r]

[@amanimagdi150]

thanks, clear illustration

[@hwang1607]

Can I use same algorithm as search in rotated sorted array

[@user-re7jf4tx5g]

Your videos are the best

[@symbol767]

I really hate Binary Search problems, Binary search by itself is simple, but its implemented in so many different weird ways, which make it really dumb..

[@crosswalker45]

I bet u hate dp too by that kinda logic 😂

[@sarvagyadwivedi2467]

@@crosswalker45 don't we all hate dp

[@crosswalker45]

@@sarvagyadwivedi2467 haha.. True

[@abhinayrk985]

You couldn't be more accurate. It's like you have to come up with a different implementation of binary search for every problem.

[@melvin6228]

Ha! Solved this on my own, my code worked but was a bit wonky. Good to see this video :) I spotted the pattern of if a part was steadily increasing or not. I didn't use the midpoint to determine any values, I just used it as a pivot and ultimately would return l or r :') Here's my wonky code (it works!) var findMin = function(nums) { let l = 0 let r = nums.length - 1 while (r - l > 1) { let m = Math.trunc( (l+r) / 2) const [isLeftIncreasing, isRightIncreasing] = isSteadilyIncreasing(nums[l], nums[m], nums[r]) if (isLeftIncreasing && isRightIncreasing) return nums[l] else if (isLeftIncreasing) { //pick right l = m } else if (isRightIncreasing) { //pick left r = m } } if (nums[l] >= nums[r]) return nums[r] else if (nums[l]

[@rustamkarimov1191]

The most effective I suppose would be: const foo = nums => { // [4,5,6,7,0,1,2,3] let [l, r] = [0, nums.length - 1] while (l < r) { let m = Math.floor((l+r) / 2) if (nums[m] >= nums[r]) l = m + 1; else r = m; } return nums[l]; }

I'm not sure this applies on Python, but when we calculate the middle element, I think it would be better to write; middle = left + (right - left) / 2; instead of middle = (left + right) / 2; to prevent arithmetic overflow. en.wikipedia.org/wiki/Binary_search_algorithm#Implementation_issues

[@NeetCode]

Thats definitely a good point!

[@yangyu7309]

python don't have int overflow issue. java and cpp definitely need left + (right - left) / 2

[@mindsetnuggets]

That's right. That's how we know a senior and a junior

[@vinaydeep26]

@@mindsetnuggets what joy did you get in putting him down, man? we all gotta learn to be more humble human beings

[@minciNashu]

could be a good practice, but the input list is constrained to max 5000 elements

[@patil_rohit]

Hey, I had quick question. Since the problem statement asks us to solve this in O(logn), don't you think using min() function (which O(m)) make this O(mlogn) ?

[@patil_rohit]

Ahh, got it. min() for two values is O(1). Thanks

[@tonyz2203]

Why do we update res on line 12 after getting the middle point?

[@JasonKim1]

mid pointer is always pointing to the potential minimum value in the array. Therefore, you want to keep updating the res variable to be checked against the new mid pointer value each iteration.

[@whizdomacademy7982]

Check the case discussed from 9.06. that will answer why we need to update res. If res would not have been updated, we would get min as 3 instead of 1 in this case.

[@KumarMukand-dm9iw]

easy way : while l < r: m = (l + r) // 2 if nums[m] > nums[r]: l = m + 1 else: r = m return nums[l]

[@numanali8545]

This is for sorted and not rotated array iguess

[@KumarMukand-dm9iw]

@@numanali8545 No it is for rotated!

[@user-gh2gw8cx2b]

@@KumarMukand-dm9iw that is such a more concise solution, thanks!

[@freyappari]

My solution: def findMin(self, nums: List[int]) -> int: l, r = 0, len(nums) - 1 while l < r: m = (l + r) // 2 if nums[m] < nums[r]: r = m else: l = m + 1 return nums[l]

[@jasonahn8658]

very simple indeed

[@josephjoestar4318]

Is it safe to assume that if a search requires O(log n) time and the list is ordered. It's most likely a binary search in some flavor or another?

[@rustamkarimov1191]

it's in fact 100% binary search

[@gusw]

Firstly: you're a genius, thanks for sharing so much on YT. Today LC came up with a use case [3,1,2] for this problem which breaks the `mid + 1` or `mid - 1` logic in this case where the answer is mid but given LEFT > MID we would to to index 0 and miss the correct answer. A little tweak on the original code should suffice tho': def findMin(self, nums: list[int]) -> int: if len(nums) == 1: return nums[0] left, right = 0, len(nums) - 1 while left = nums[left]: left = mid else: right = mid

[@stevenmo1586]

it still works right? the answer is MID but LEFT > MID, we capture the minimum already by doing min(res, nums[mid]) before comparing LEFT > MID... the minimum will remain as 1 throughout the entire loop. Your answer is a little better as we don't need to store a variable for the mininum value and perform a comparison to get the minumum value per loop. Great job!

[@ikthedarchowdhury8947]

Hey GUstavo, thanks for your insight! I would love to talk to you more about problem solving. Is it possible I can contact you in any way like DIscord or Twitter?

[@danmuji7585]

hm..does len(arr) count as time complexity of O(N)?

[@devonchia5976]

I have another solution based on his logic where I don't keep track of the min res value: l, r = 0, len(nums)-1 while nums[l] > nums[r]: mid = (l+r)//2 if nums[mid] >= nums[l]: l = mid + 1 else: r = mid return nums[l]

[@PippyPappyPatterson]

Why do we need line 12, `res = min(res, nums[m])`? Wouldn't it be caught if we just assigned `l = m` or `r = m` instead of `= m ± 1`?

[@ganeshkamath89]

I think because it saves time. Example has just 5 inputs so it might seem to be less useful.

[@PippyPappyPatterson]

@@ganeshkamath89 I've been practicing it without storing the minimum result for a few months now. I don't think you need to store the minimum. I just return the `nums[m]` value.

[@ganeshkamath89]

@@PippyPappyPatterson Thanks. You are right. I tried this code change and it worked for me also 😀

[@PippyPappyPatterson]

@@ganeshkamath89 ofc, good luck internet traveler

[@EduarteBDO]

I did this solution quite different by checking if middle is < middle-1 I can itentify the lowest number: def findMin(self, nums: list[int]) -> int: l, r = 0, len(nums) - 1 while l nums[r]: l = middle+1 else: r = middle-1 return nums[l]

[@aviranawat]

Waiting for your 752. Open the Lock video. Thanks in advance.

[@fsteve6443]

ur in luck he just uploaded it

[@orewamusashides]

Doesn't initializing right pointer to the end of the array itself take O(n) time? Languages like Python might have under the hood optimizations to do this more efficiently, but from algorithmic perspective, if we have to iterate through the array once to initialize the right pointer, wouldn't it be more efficient to just find the minimum in that iteration itself?

[@rahulsbhatt]

Such a great explanation!

[@adamabdelmalak7095]

after the condition if nums[m] >= nums[l]: you need to update res to nums[l] because according to the condition it is less than nums[m](our current res) and this is the last time we'll be visiting the current nums[l] (since we update l to m+1)

[@The6thProgrammer]

We are always terminating if nums[l] < nums[r] to handle this, so there is no need to explicitly check nums[l] at each iteration. For instance if nums[m] >= nums[l] we know that nums[l] is also greater than or equal to nums[r] (because we checked this condition first)... therefore there is no way nums[l] at that point will be the minimum result since there is a smaller value on the right side of the array and we update l to mid + 1 to search the right side. Put more simply... because we always check nums[l] < nums[r] we are always guaranteed to terminate and set the result to nums[l] if nums[l] is ever the min.

[@sergiofranklin8809]

more consice solution: def findMin(self, nums: List[int]) -> int: l, r = 0, len(nums)-1 while l=nums[r]: l = mid+1 else: r = mid return nums[l]

[@vrushankdesai715]

My solution which I think is more intuitive: class Solution: def findMin(self, nums: List[int]) -> int: start , end = 0 ,len(nums) - 1 curr_min = float("inf") while start < end : mid = (start + end ) // 2 if(nums[mid+1] < nums[mid]): return nums[mid+1] # right has the min if nums[mid] > nums[end]: start = mid + 1 # left has the min else: end = mid return nums[start]

[@tmjz7327]

I had something similar.

[@JDoesMuzik]

i think you should clarify what right portion and left portion is if you're referring to the original array sorted

[@himanshu6489]

absolutely

[@user-zv8mm6rj7r]

Isn't the time complexity of min() function O(n), which kinda defeats the purpose of using binary search to find the solution in O(logn)? If we must use min(), we can just do `return min(nums)` at that point? Someone please explain, I am a little confused. Thanks!

[@Shonia]

when using min(x,y) for only two values, it is constant time but if you give it a list, it will be O(n)

[@brindhadhinakaran9672]

Thanks

[@sanjitapokhrel7245]

Why does it not work for [3,2 ]?

[@timetaser]

Unfortunately this algorithm does not work for test cases such as: [2,1] or [3,1,2]

[@JamesBond-mq7pd]

i found more shorter way: class Solution: def findMin(self, nums: List[int]) -> int: l, r = 0, len(nums) - 1 while l

[@OGKix]

wow this is so much better and is way easier to remember

[@ReArNiDcOM]

You mention that the left sorted portion is always going to have values > the right sorted portion. In the event that the array has not been rotated or rotated n - 1 times (which would produce the same array) then wouldn't that statement not be true? Ex: [0,1,2,3,4,5,6,7] ... m = array[4] ... array[4] == 3 ... 3 >= 0 ... we are in the left sorted portion ... all values of the right sorted portion are greater than the left. Maybe I am confused but if someone could clarify I would greatly appreciate it.

[@ReArNiDcOM]

Sorry at 8:00 he cleared this up. In the event that left < right then we are in a sorted array. Given left < result then result = left return result.

[@sanooosai]

thnak you

[@will-iy9gu]

damn this problem broke my brain for some reason lol

[@taco564]

You're the best

[@sarthakmahapatra4572]

You are awesome

[@kevinq8753]

class Solution: def findMin(self, nums: List[int]) -> int: return min(nums)

[@ilkerbaks7942]

class Solution { public: int findMin(vector& nums) { sort(nums.begin(),nums.end()); return nums[0]; } };

[@NischitSapkota]

since the best sorting algorithm is nlogn , your solution is going to be nlogn , which is worse than linear search(n) let alone binary search (logn)

[@AryanRao-v3h]

return min(nums) works as well

[@evynsrefuge]

no its doesn't, that's not log n time complexity, thats n. Even though it passes in leetcode it's wrong due to the problem constraints.

[@InfoBuzz1130]

I did Arrays.sort(nums); return nums[0]; :D :D

[@mohamadilhamramadhan6354]

The funny thing is I test my naive solution which o(n) in Javascript: function min(nums) { return Math.min(...nums); } and it beats 23% of other solutions which used binary search 🤣

[@obinnaikeh1928]

Not sure why, but simply using "return min(nums)" (in Python) seems to run faster than the binary search algorithm solution.

[@cloud5887]

what is "min" doing under the hood?

[@adarshvats8003]

*'min' use O(N) time to search for the minimum element in an array. * It uses linear search. * The time taken shown in leetcode doesn't provide you the actual time taken.

[@vaishaliagrawal4781]

@@adarshvats8003 but in this solution, instructor used min function so what's point of using in code then using in first place.

[@adarshvats8003]

@@vaishaliagrawal4781 min(array) gives you minimum of array in O(N) but if we write min(x, y) gives minimum in O(2) which is a linear operation. Thus the code still remains O(logn). I hope this helps!!

[@vaishaliagrawal4781]

@@adarshvats8003 Thanks, make sense

[@chanchalagrawal9548]

It does not work for case when minimum is at mid. e.g: [3,1,2]

[@himanshu6489]

does it even work for [1,2,3] ?

[@edwardteach2]

U a BST God🎉

[@JDoesMuzik]

lost when you just assume mid will be at 1? how can you explain the set up

[@lch99310]

May I know why you use // instead of / in m.

[@NeetCode]

In python a single '/' will evaluate to decimal division (e.g. 1 / 2 = 0.5), where as '//' evaluates to integer division which is the default for most languages (e.g. 1 / 2 = 0)

[@illu1na]

My gawd, every one of these binary search problems I get some edge cases wrong due to these tiny but important details of settings r = m (instead of m - 1) or having l start from 1 instead of 0 (koko eating bananas). It's super frustrating

[@jasonahn8658]

don't worry you'll get there. one step at a time

[@illu1na]

@@jasonahn8658thanks man.

[@NAGARJUNAKOLLOJU]

while(l Think why! else h = mid; } } For anyone who is struggling, I break these type of questions to 2 cases. (mid is in sorted sub_array, mid is not in sorted_subarray). Write cases accordingly!

[@arina1193]

def findMin(self, nums: List[int]) -> int: bad = -1 good = len(nums) - 1 while good - bad > 1: candidate = (bad + good) // 2 if nums[candidate] < nums[good]: good = candidate else: bad = candidate return nums[good]

[@algorithmo134]

Can you do binary cameras tree leetcode?

[@nomad_1997]

The code presented in the video is incorrect, it's different from even the Python code submitted on the website. Can you please fix the video?

[@JamesBond-mq7pd]

MORE EASIER WAY! def findMin(self, nums: List[int]) -> int: res = float("inf") l, r = 0, len(nums) - 1 while l nums[r]: l = m + 1 else: r = m - 1 return res

[@adilkhalid1446]

you can just return nums[L] at the end and avoid the res

[@ianokay]

You state the rules: "If our middle pointer happens to be in the right sorted portion, then we want to search to the left; **if our middle is in the left sorted portion we want to search to the right**". And later state: "If we ever got to a portion of the array that's completely sorted we would just **take the leftmost value and see if it's smaller than the current result and stop our binary search.**" This statement completely conflicts with the algorithm of focus, which says **if the leftmost value is smaller we search to the right**. So do we search to the left or "stop our binary search"? So are there two algorithms rules at play here or what? I'm guessing yes, but you said an entirely conflicting rule pretty flippantly without clarifying this is an important rule caveat and consideration.

[@klyesam4006]

Isn't binary search already log(n) why not just sort it?

[@klyesam4006]

Oh sorting is nLog(n)

[@seibern]

return min(nums) did the trick for me but I don't think thats intended

[@Rahul-eh3rf]

No because that is not in O(log n)

[@Lambyyy]

@@Rahul-eh3rf What about my code here: l, r = 0, len(nums) - 1 while l < r: if nums[r] > nums[r - 1]: r -= 1 elif nums[r] < nums[r - 1]: return min(nums[l], nums[r]) if l == r: return nums[l] # if nums[r] can move down then keep nums[l] # if nums[r] cannot move down compare value with nums[l] and return smallest value # if index l and index r are the same, return nums[l] everything fine? It passes all test cases but not sure if O(log n).

[@tahsinamio2639]

@@Lambyyy It's O(n) because you are essentially comparing every num against left num. A O(logn) solution is possible here if the problem size is halved every step.

[@Lambyyy]

@@tahsinamio2639 Ah okie, thank you!

[@indhumathi5846]

understood

[@AbhishekSingh-tz3uv]

Explanation of rotated sorted array is much better in kzbin.info/www/bejne/i2m7doGtnZ2Cr5o Watch it before giving a try to this one.

[@hoyinli7462]

gd video!

[@Suraj-wt8hn]

Nice Explanation!! Another approach in O(logn) time will be Two pointer strategy, I solved it using the following approach

[@aurkom]

``` def findMin(self, nums: List[int]) -> int: left = 0 right = len(nums) - 1 while (left < right): mid = (left+right)//2 if (nums[mid]

[@idexq]

min(nums) got accepted)

[@RN-jo8zt]

here we are doing r=mid instead of r=mid-1?

[@ritiksaxenaofficial]

Great explanation

[@ritiksaxenaofficial]

My code: class Solution: def findMin(self, nums: List[int]) -> int: low = 0 high = len(nums)-1 while low

[@adityakunchur6209]

Why not implement the binary search recursively rather than using the while loop? It's still O(logn) right?

[@durgaprasadreddypeddireddy8740]

I believe it is done in this to limit the stack usage.

[@TheRandomdude136]

I have a simpler alternative that allows you to not keep track of the minimum, here it is: class Solution: def findMin(self, nums: List[int]) -> int: start, end = 0, len(nums) - 1 while start - end > 1: # if middle exists mid = (start + end) // 2 if nums[mid] > nums[end]: start = mid + 1 else: end = mid return min(nums[start], nums[end])

[@karamany9870]

C++ solution: class Solution { public: int findMin(vector& nums) { int i = 0 ; int j = nums.size() - 1; int mid = (i+j)/2; if(nums.size()==1) { return nums[0]; } /* idea: use binary search. If the value to left of mid is smaller than the right pointer, then move right pointer to mid Otherwise, move left pointer to mid */ while(i

[@jxswxnth]

No need to do any storing and comparing. Simple Binary searching here.. def findMin(nums,l,h): mid= (l+h)//2 if(nums[l]nums[h]): return h return findMin(nums,l,mid)

[@harishsn4866]

I hope you can make a video about Binary Search Templates and help us understand it better. Thank you. class Solution: def findMin(self, nums: List[int]) -> int: low, high = 0, len(nums) - 1 while low < high: mid = (low + high) // 2 if nums[mid] < nums[high]: high = mid elif nums[mid] > nums[high]: low = mid + 1 return nums[high] #nums[low]

[@harutto5896]

What about this [5,1,2,3,4,] Not every value in the left portion is bigger than in the right portion

[@__priyanshu__sharma____]

If an array is rotated to the its size times then this may verdict your answer

[@djhaik]

what does 'verdict' your answer mean?

[@__priyanshu__sharma____]

@@djhaik the answer may be wrong.

[@kaushikmahanta6463]

please code using c++ too

[@kartikaysingh007]

int low = 0, high = arr.size() - 1; int ans = INT_MAX; while (low

[@shivamrawat108]

If we are using the min() function then why not just take the minimum of the original array and return the value.

[@evynsrefuge]

that would be n time complexity as you would have to search through the whole array. Binary search splits the search time by 2 hence log n time complexity. And the min function being used in this example is only used for the 2 values at a time, not the whole array

[@shivamrawat108]

@@evynsrefugemakes sense thanks

[@pammugaadu]

Thank you for your valuable time. I really appreciate. If anyone is looking for Java Code: public static int findMinimum(int[] input) { if (input == null || input.length == 0) { throw new IllegalArgumentException("Invalid input passed"); } int left = 0, right = input.length - 1, mid = 0; while (left != right) { mid = (left + right) / 2; if (input[mid] >= input[left]) { left = mid + 1; } else { right = mid - 1; } } return input[mid]; }

[@yilmazbingol4838]

class Solution: def findMin(self, nums: List[int]) -> int: low, high = 0, len(nums) - 1 while low < high: mid = (low + high) // 2 if nums[mid] > nums[high]: low = mid + 1 else: high = mid return nums[low]

[@christianmorabito4148]

I tried this too which I thought was great, but it doesn't work for this list: nums = [12, 0, 1, 2, 3, 4, 5, 6, 9, 10, 11]

[@christianmorabito4148]

Sorry, I was returning m (mid variable) instead of l (low variable).

[@nsaid26]

Good explanation, however, I think we can improve it keeping L and R, but looping length/2 times in both direction, if nums[L] > nums[L+1] then L is the position of the minimum or if nums[R] < nums[R-1] then position R holds the minimum: // C# for (int i = 0, j = nums.Length - 1; i < nums.Length / 2; i++, j--) { if (nums[i] > nums[i + 1]) return nums[i + 1]; if (nums[j] < nums[j - 1]) return nums[j]; } return nums[0];

[@theflabbygentleman9292]

you're supposed to solve it in logarithmic time

[@durgaprasaddevarakonda8623]

class Solution: def findMin(self, nums: List[int]) -> int: try: for ele in range(len(nums)): if nums[ele] > nums[ele+1]: return nums[ele+1] except: return nums[0]

[@podgorniy.r]

2:29 3:18 8:05

[@mihaieugen1280]

Bro breathe

[@wotizit]

Why

[@manpt123]

1 line solution, just ""return min(nums)" thats it

[@talhahashim6905]

bro o(logn) is the requirement. you are mentioning o(n) approach

[@__________________________6910]

Hard