二分查找

查找目标值o

func BinarySearch(a []int, o int, begin, end int) int {
    if end >= len(a) || begin < 0 || begin >= end {
        return -1
    }

    for begin < end {
        mid := (begin + end) >> 1
        if a[mid] > o {
            end = mid
        } else if a[mid] < o {
            begin = mid + 1
        } else {
            return mid
        }
    }

    return -1
}

查找最右边的元素

func BinarySearchRight(a []int, o int, begin, end int) int {
    if end >= len(a) || begin < 0 || begin >= end {
        return -1
    }

    for begin < end {
        mid := (begin + end) >> 1
        if a[mid] > o {
            end = mid
        } else if a[mid] < o {
            begin = mid + 1
        } else {
            if mid+1 < end && a[mid+1] == o {
                begin = mid + 1
            } else {
                return mid
            }
        }
    }

    return -1
}

查找最左边的元素

func BinarySearchLeft(a []int, o int, begin, end int) int {
    if end >= len(a) || begin < 0 || begin >= end {
        return -1
    }

    for begin < end {
        mid := (begin + end) >> 1
        if a[mid] > o {
            end = mid
        } else if a[mid] < o {
            begin = mid + 1
        } else {
            if mid-1 >= 0 && a[mid-1] == o {
                end = mid
            } else {
                return mid
            }
        }
    }

    return -1
}