二分查找方法

二分查找方法

算法描述：在一组有序数组中，将数组一分为二，将要查询的元素和分割点进行比较，分为三种情况

• 相等直接返回
• 元素大于分割点，在分割点右侧继续查找
• 元素小于分割点，在分割点左侧继续查找

时间复杂： O(lgn).

要求

• 必须是有序的数组，并能支持随机访问

变形

• 查找第一个值等于给定的
  • 在相等的时候做处理，向前查
• 查找最后一个值等于给定的值
  • 在相等的时候做处理，向后查
• 查找第一个大于等于给定的值
  • 判断边界减1
• 查找最后一个小于等于给定的值
  • 判断边界加1

实际应用

• 用户ip区间段查询
• 用于相似度查询

package sort

import "fmt"

func bin_search(arr []int, finddata int) int {
    low := 0
    high := len(arr) - 1
    for low <= high {
        mid := (low + high) / 2
        fmt.Println(mid)
        if arr[mid] > finddata {
            high = mid - 1
        } else if arr[mid] < finddata {
            low = mid + 1
        } else {
            return mid
        }
    }
    return -1
}

func main() {
    arr := make([]int, 1024*1024, 1024*1024)
    for i := 0; i < 1024*1024; i++ {
        arr[i] = i + 1
    }
    id := bin_search(arr, 1024)
    if id != -1 {
        fmt.Println(id, arr[id])
    } else {
        fmt.Println("没有找到数据")
    }
}