Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
Find the minimum element.
You may assume no duplicate exists in the array. Example 1:
Input: [3,4,5,1,2]
Output: 1
Example 2:
Input: [4,5,6,7,0,1,2]
Output: 0
Tags: Math, String
There is an ordered array, assuming that starting from a certain number, the numbers behind it are placed in front of the array in order. (i.e. [0,1,2,4,5,6,7] may become [4,5,6,7,0,1,2]). Please find the smallest element in the array. The array does not contain duplicate elements.
(二分) O(logn)
There is a common technique to deal with this kind of problem: if you don't want to deal with boundary cases, such as when the array has only two or three numbers, the code will go wrong. When the length of the array is too short(in this question, we judge that the length of the array is less than 5), we can directly do it in a violent cycle; when the array has a certain length, we can use two points to do it. Doing so will not affect the time complexity of the algorithm, but it will shorten the time to write code. For ease of understanding, we draw the numbers in the array in a two-dimensional coordinate system, the abscissa indicates the subscript of the array, and the ordinate indicates the value, as shown below:
We will find that the numbers nums[i]nums[i] in front of the minimum value in the array are all satisfied: nums[i]≥nums[0]nums[i]≥nums[0\ ], where nums[n−1]nums[n−1] is the last element of the array; and the numbers after the minimum value in the array (including the minimum value) do not meet this condition. So we can dichotomize the location of the minimum. Also, don't forget to handle the special case where the array is completely monotonic. Time complexity analysis: binary search, so the time complexity is O(logn)O(logn).
func findMin(nums []int) int {
if nums[len(nums)-1] > nums[0] {
return nums[0]
}
l, r := 0, len(nums)-1
for l < r {
mid := l + (r-l)>>1
if nums[mid] >= nums[0] {
l = mid + 1
} else {
r = mid
}
}
return nums[l]
}If you love data structures, algorithms, and LeetCode as much as I do, you can follow my LeetCode solution on GitHub：awesome-golang-algorithm