使用Go实现二分查找（Binary Search）

二分查找的特点

1. 有序集合
2. 分治思想
3. 时间复杂度O(logn)

二分查找的局限性

1. 依赖有序表结构
2. 数据要有序
3. 数据量太小不适合二分查找
4. 数据量太大也不适合二分查找

Go实现

1. 有序数组不存在重复情况

// 循环实现
func bsearch(sort [] int, value int) int {
    lew := 0
    high := len(sort) - 1
    for lew <= high {
        var mid int = lew + ((high - lew) >> 1)
        if value == sort[mid] {
            return value
        }
        // +1 与 -1 不这样写会产生死循环
        if value < sort[mid] {
            high = mid - 1
        }
        if value > sort[mid] {
            lew = mid + 1
        }
    }
    return -1
}

// 递归
func bsearchInternally(find [] int, value int, lew int, high int) int {
    if lew > high {
        return -1
    }
    var mid int = lew + ((high - lew) >> 1)
    if find[mid] == value {
        return value
    }
    if find[mid] < value {
        lew = mid + 1
    }
    if find[mid] > value {
        high = mid - 1
    }
    return bsearchInternally(find, value, lew, high)
}

2. 有序有重复数据

变体一 （会用两种解法来做，后面的只会使用一种）： 查找第一个值等于给定值的元素
// 第一种解法
func firstBsearch(zeus [] int, thearchy int) int {
    lew := 0
    high := len(zeus) - 1
    for lew <= high {
        mid := lew + ((high - lew) >> 1)
        // 精华 思想是一样的人家的代码的实现超乎你想象
        if zeus[mid] >= thearchy {
            high = mid - 1
        } else {
            lew = mid + 1
        }
    }
    if lew < len(zeus) && zeus[lew] == thearchy {
        return zeus[lew]
    }
    return -1;
}

// 第二种解法
func firstBsearchs(zeus [] int, thearchy int) int {
    lew := 0
    high := len(zeus) - 1
    for lew <= high {
        mid := lew + ((high - lew) >> 1)
        if zeus[mid] > thearchy {
            high = mid - 1
        } else if zeus[mid] < thearchy {
            lew = mid + 1
        } else {
            if zeus[mid-1] == thearchy {
                high = mid - 1
            } else {
                return zeus[mid]
            }
        }
    }
    return -1;
}

变体二：查询给定的最后一个值
// 查询给定的最后一个值
func lastBsearch(zeus [] int, thearchy int) int {
    lew := 0
    high := len(zeus) - 1
    for lew <= high {
        mid := lew + ((high - lew) >> 1)
        if zeus[mid] > thearchy {
            high = mid - 1
        } else {
            lew = mid + 1
        }
    }
    if high < len(zeus) && zeus[high] == thearchy {
        return zeus[high]
    }
    return -1;
}
变种三： 查找大于等于给定值的
// 大于等于给定值的
func geSelected(zeus [] int, selected int) int {
    lew := 0
    high := len(zeus) - 1
    for lew <= high {
        mid := lew + ((high - lew) >> 1)
        if zeus[mid] >= selected {
            high = mid - 1
        } else {
            lew = mid + 1
        }
    }
    // 这里的逻辑很重要
    if high < len(zeus) && zeus[high] == selected {
        return zeus[high]
    } else if high+1 < len(zeus) && zeus[high+1] >= selected {
        return zeus[high+1]
    }
    return -1;
}

变种四：查找小于等于给定值的
// 小于等于给定值的
func leSelected(zeus [] int, selected int) int {
    lew := 0
    high := len(zeus) - 1
    for lew <= high {
        mid := lew + ((high - lew) >> 1)
        if zeus[mid] > selected {
            high = mid - 1
        } else {
            lew = mid + 1
        }
    }
    // 这里的逻辑很重要
    if lew < len(zeus) && zeus[lew] == selected {
        return zeus[high]
    } else if lew-1 < len(zeus) && zeus[lew-1] <= selected {
        return zeus[high-1]
    }
    return -1;
}


func main() {
    // 简单二分查找
    var sort = []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
    i := bsearch(sort, 7)
    internally := bsearchInternally(sort, 7, 0, len(sort)-1)
    fmt.Println(i)
    fmt.Println(internally)
    // 二分查找变种
    var athena = []int{1, 2, 3, 4, 4, 6, 6, 8, 9, 10}
    a := firstBsearch(athena, 6)
    fmt.Println(a)
    b := lastBsearch(athena, 6)
    fmt.Println(b)
    c := geSelected(athena, 4)
    fmt.Println(c)
    d := leSelected(athena, 7)
    fmt.Println(d)
}

有什么问题欢迎指出。