二分算法之查找最左位置

miloyang
0 评论
/ /
860 阅读
/
992 字
10 2023-08

在有序数组中给定一个数num,查找大于num的最左坐标。

也是通过二分查找,跟 搜索算法之二分查找 很像,算是一个进阶版本。
如有序数组为[3,12,18,20,24] 给定一个数为19, 18<19<20,则最左侧的数就是20,下标为3.

释义

最左二分查找过程图示

代码

 // 3, 12, 18, 20, 24  num=21
func SearchLeftBinary(arr []int, num int) {
    left := 0             // 左游标
    right := len(arr) - 1 // 右游标
    var middle int
    ans := -1 //定义目前找到的最左侧下标,初始为找不到

    for right >= left {
        middle = left + (right-left)>>1 // 位移 >>是/2的另一种表达
        if arr[middle] >= num {
            //说明num在m的左边,则left不动
            right = middle - 1
            ans = middle //说明目前已经是最左边,先记录下
        } else if arr[middle] < num {
            // 说明num在m的游标,则right不动
            left = middle + 1
        }
    }
    fmt.Println(ans) // 4
}

时间复杂度为 log(N)

人未眠
工作数十年
脚步未曾歇,学习未曾停
乍回首
路程虽丰富,知识未记录
   借此博客,与之共进步