在有序数组中给定一个数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)