public class Solution {
public int FindMin(int[] nums) {
int li = 0; //low index
int hi = nums.Length-1; //high index
while(hi>li)
{
int midi = li+(hi-li)/2;
if (nums[midi] < nums[hi])
{
hi = midi;
}
else
{
li = midi+1;
}
}
return nums[li];
}
}
In this solution, we will search the answer from every remaining half after iteration (1/2 ➡ 1/4 ➡ 1/8 … etc )
Time Complexity : O(log n)
⚠️Another try – Linq – Enumerable.Min
public class Solution {
public int FindMin(int[] nums) {
return nums.Min();
}
}
One line code, so clear and simple.
But what about it’s time complexity? I can’t found the answer on Google…
Maybe we can find something on the official document? ( *1 )
Fine.. That is not the answer I want.
Suddenly, an idea came to me. Official source code !! ( *2 )
Oh! Just an easy iteration, so it’s time complexity will be O(n).
Time Complexity : O(n)
Java Solution
Solution1
class Solution {
public int findMin(int[] nums) {
int li = 0; //low index
int hi = nums.length-1; //high index
while(hi>li)
{
int midi = li+(hi-li)/2;
if (nums[midi] < nums[hi]) {
hi = midi;
} else {
li = midi+1;
}
}
return nums[li];
}
}
Time Complexity : O(log n)
Python3 Solution
Solution1
class Solution:
def findMin(self, nums: List[int]) -> int:
li = 0 #low index
hi = len(nums)-1 #high index
while(hi>li):
midi = int(li+(hi-li)/2)
if (nums[midi] < nums[hi]):
hi = midi
else:
li = midi+1
return nums[li]
Time Complexity : O(log n)
JavaScript Solution
Solution1
/**
* @param {number[]} nums
* @return {number}
*/
var findMin = function(nums) {
var li = 0; //low index
var hi = nums.length-1; //high index
while(hi>li)
{
var midi = parseInt(li+(hi-li)/2,10);
if (nums[midi] < nums[hi])
{
hi = midi;
}
else
{
li = midi+1;
}
}
return nums[li];
};
Conclusion
🧡If my solution helps, that is my honor!
🧡You can support me by clicking some ad, Thanks a lot
✅If you got any problem about the explanation or you need other programming language solution, please feel free to let me know (either leave a comment or contact me by Messenger is ok!)
ai_front = {"insertion_before":"BEFORE","insertion_after":"AFTER","insertion_prepend":"PREPEND CONTENT","insertion_append":"APPEND CONTENT","insertion_replace_content":"REPLACE CONTENT","insertion_replace_element":"REPLACE ELEMENT","visible":"VISIBLE","hidden":"HIDDEN","fallback":"FALLBACK","automatically_placed":"Automatically placed by AdSense Auto ads code","cancel":"Cancel","use":"Use","add":"Add","parent":"Parent","cancel_element_selection":"Cancel element selection","select_parent_element":"Select parent element","css_selector":"CSS selector","use_current_selector":"Use current selector","element":"ELEMENT","path":"PATH","selector":"SELECTOR"};