go 二分查找

二分查找

给定一个有序数组 [1,2,4,6,8,8,10]，再给定一个target值，此处以 8 为例，一般有4个查询目标

1. 从左向右第一个大于等于target的值的下标
2. 从左向右第一个大于target的值的下标
3. 从左向右最后一个小于等于target的值的下标
4. 从左向右最后一个小target的值的下标

3 和 4 是 1 和 2 的对立面，而1 和 2本质上是同一个目标

code

package main
import "fmt"
var arrs = []int{1,2,4,6,8,8,10}
func main () {

    fmt.Printf("before arr: %v\n", arrs)

    up_equal := binary_search_up_equal(arrs, 8)

    fmt.Printf("the index of element which first ge %d is %d\n", 8, up_equal)

    up := binary_search_up(arrs, 8)

    fmt.Printf("the index of element which first g %d is %d\n", 8, up)

    down_equal := binary_search_down_equal(arrs, 8)

    fmt.Printf("the index of element which first le %d is %d\n", 8, down_equal)

    down := binary_search_down(arrs, 8)

    fmt.Printf("the index of element which first l %d is %d\n", 8, down)
}

// 第一个大于等于 8
func binary_search_up_equal(arrs []int, target int) int {
    l, r := 0, len(arrs) - 1
    for l < r {
        mid := (l+r) / 2
        if arrs[mid] < target {
            l = mid + 1
        } else {
            r = mid
        }
    }
    return l
}

// 第一个大于 8
func binary_search_up(arrs []int, target int) int {
    l, r := 0, len(arrs) - 1
    for l < r {
        mid := (l+r) / 2
        if arrs[mid] <= target {
            l = mid + 1
        } else {
            r = mid
        }
    }
    return l
}

// 最后一个小于等于 8
func binary_search_down_equal(arrs []int, target int) int {
    l, r := 0, len(arrs) - 1
    for l < r {
        mid := (l+r+1) / 2
        if arrs[mid] > target {
            r = mid - 1
        } else {
            l = mid
        }
    }
    return l
}

// 最后一个小于 8
func binary_search_down(arrs []int, target int) int {
    l, r := 0, len(arrs) - 1
    for l < r {
        mid := (l+r+1) / 2
        if arrs[mid] >= target {
            r = mid - 1
        } else {
            l = mid
        }
    }
    return l
}

返回值

• before arr: [1 2 4 6 8 8 10]
• the index of element which first ge 8 is 4
• the index of element which first g 8 is 6
• the index of element which first le 8 is 5
• the index of element which first l 8 is 3