Golang二分法查找

使用二分查找需要数组是有序的。

比如在升序排列的数组中，将数组中间位置的数据与目标数据比较，如果相等则查找成功；否则按照中间位置把数组分为两部分，如果中间位置大于目标数据，则在前半部分中以取中心点的方式继续比较，否则查找后半部分。

func main()  {
    array := []int{1, 2, 3, 4, 5}
    if index, ok := BinarySearch(array, 2); ok {
        fmt.Printf("目标数据下标是：%v", index)
    } else {
        fmt.Println("没有找到")
    }
}

func BinarySearch(arr []int, targetValue int) (int, bool) {
    leftIndex := 0 // 左下标
    rightIndex := len(arr) - 1 // 右下标

    // 若leftIndex大于rightIndex，表示数组中没有该数据
    for leftIndex <= rightIndex {
        // 中间下标
        middleIndex := (leftIndex + rightIndex) / 2

        if arr[middleIndex] > targetValue {
            // 目标数据在左半边
            rightIndex = middleIndex - 1
        } else if arr[middleIndex] < targetValue {
            // 目标数据在右半边
            leftIndex = middleIndex + 1
        } else {
            // 找到目标数据
            return middleIndex, true
        }
    }
    return -1, false
}