2020-11-13:手写代码:局部最小值问题。数组无序,相邻元素不等。如何求极小值?

福大大架构师每日一题 · · 415 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

福哥答案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
}

执行结果如下:


image.png

有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:福大大架构师每日一题

查看原文:2020-11-13:手写代码:局部最小值问题。数组无序,相邻元素不等。如何求极小值?

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

415 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传