福哥答案2020-11-13:
二分法。有时候数组无序,同样可以采用二分法。这道题考察的是全局观,左边下降趋势,右边上升趋势,函数图像呈凹形,必有极小值。中左值和中值呈上升趋势,中值右边可以直接舍弃;中值和中右值呈下降趋势,中值左边可以直接舍弃。
golang代码如下:
package class01
import (
"fmt"
"testing"
)
//局部最小值问题
/*
求其中一个极小值
数组无序,但相邻元素不等
*/
//go test -v -test.run TestBSAwesome
func TestBSAwesome(t *testing.T) {
fmt.Println("----------------------")
if true {
s := []int{3, 2, 4, 8, 7, 12}
fmt.Println("数组:", s)
ret := GetLessIndex(s)
fmt.Println("结果序号:", ret)
fmt.Println("----------------------")
}
}
func GetLessIndex(arr []int) int {
arrlen := len(arr)
//数组没元素
if arrlen == 0 {
return -1 // no exist
}
//第一个元素
if arrlen == 1 || arr[0] < arr[1] {
return 0
}
//最后一个元素
if arr[arrlen-1] < arr[arrlen-2] {
return arrlen - 1
}
left := 1
right := arrlen - 2
mid := 0
for left < right {
mid = left + (right-left)>>1
if arr[mid] > arr[mid-1] { //中值大于中左值,舍弃右边
right = mid - 1
} else if arr[mid] > arr[mid+1] { //中值大于中右值,舍弃左边
left = mid + 1
} else {
return mid
}
}
return left
}
执行结果如下:
有疑问加站长微信联系(非本文作者)