二分查找

正常的二分查找

package main

import "fmt"

func main() {
    // 二分查找要求数据必须是有序的。
    nums := []int{1, 3, 5, 7, 9, 11, 13, 15}

    target := 9
    index := BinarySearch(nums, target)
    fmt.Printf("查找 %d 的结果下标: %d\n", target, index)

    target = 10
    index = BinarySearch(nums, target)
    fmt.Printf("查找 %d 的结果下标: %d\n", target, index)
}

// BinarySearch 在有序切片中查找目标值。
// 找到则返回下标，找不到返回 -1。
func BinarySearch(nums []int, target int) int {
    left := 0
    right := len(nums) - 1

    for left <= right {
        // 取中间下标。
        // 这种写法可以避免 left 和 right 很大时直接相加的潜在溢出问题。
        mid := left + (right-left)/2

        if nums[mid] == target {
            return mid
        }

        if nums[mid] < target {
            // 目标值在右半边。
            left = mid + 1
        } else {
            // 目标值在左半边。
            right = mid - 1
        }
    }

    return -1
}

反转二分查找