1. 二分法查找

百度百科： 二分法查找适用于数据量较大时，但是数据需要先排好顺序

常见的必考题，而且经常要求手写，甚至需要会写多种形式

时间复杂度 O(log2n)

1.1.1. 循环

func binarySearch(arr []int,k int) int {

    low,high := 0,len(arr)-1
    for low <= high {
        mid := (low + high) >> 1
        if k > arr[mid] {
            low = mid + 1
        } else if k < arr[mid] {
            high = mid - 1
        } else {
            return mid
        }
    }
    return 0
}

1.1.2. 递归

func Search(arr []int,k int) int {
    return binarySearch(arr,k,0,len(arr)-1)
}

func binarySearch(arr []int,k,l,h int) int {
    if l > h {
        return -1
    }

    m := (l + h) >> 1

    if k > arr[m] {
        return binarySearch(arr,k,m+1,h)
    } else if k < arr[m] {
        return binarySearch(arr,k,l,m-1)
    } else {
        return m
    }

}