欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

153. 寻找旋转排序数组中的最小值-M

程序员文章站 2022-03-15 10:17:34
...

153. 寻找旋转排序数组中的最小值(find-minimum-in-rotated-sorted-array)

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

你可以假设数组中不存在重复元素。

示例 1:

输入: [3,4,5,1,2]
输出: 1
示例 2:

输入: [4,5,6,7,0,1,2]
输出: 0
  • 分析

    这里虽然整体无序,但中间划分后,总有一边是有序的,故可以很  
    好的使用二分查找,仍是使用模板,细分题目要求
    
  • code

package main
import "fmt"
func findMin(nums []int) int {
	s:=len(nums)
	if nums[0]<nums[s-1]{
		return nums[0]
	}
	var i,j int
	j=s-1
	for i<j{
		m:=i+(j-i)/2
		fmt.Println(i,j,m)
		if nums[m]<nums[s-1]{
			j=m
		}else{
			i=m+1
		} 
	}//最终i==j(确保i和j,只有一个m+1,另一个变化是要等于m)
	return nums[i]
}
func main(){
	fmt.Println(findMin([]int{4,5,6,7,0,1,2}))
	fmt.Println(findMin([]int{3,4,5,1,2}))
}
相关标签: 二分查找