折半/二分查找

package main

import "fmt"

var Time = 1

// 折半 搜索
func main() {

    index := binarySearch([]int{1, 2, 3, 4, 9}, 9)
    if index < 0 {
        fmt.Print("failed")
    } else {
        fmt.Println("success index:", index)
    }

    fmt.Println("===second way:", binarySearch2([]int{1, 2, 3, 4, 9}, 0, 4, 9, &Time))
    fmt.Println("---Time:", Time)
}

func binarySearch(list []int, key int) int {
    if 0 == len(list) {
        return -1
    }

    time := 0
    low := 0
    high := len(list) - 1

    for low <= high {
        time++
        mid := (low + high) / 2

        if key < list[mid] {
            high = mid - 1
        } else if key > list[mid] {
            low = mid + 1
        } else {
            fmt.Println("find times:", time)
            return mid
        }
    }

    return -1
}

func binarySearch2(list []int, low, high, key int, Time *int) int {
    if low > high {
        return -1
    }
    *Time++
    mid := (low + high) / 2
    if key < list[mid] {
        return binarySearch2(list, low, mid-1, key, Time)
    }
    if key > list[mid] {
        return binarySearch2(list, mid+1, high, key, Time)
    }
    return mid
}