04. 二分查找方法
<h1>1. 二分查找方法</h1>
<p>算法描述：在一组有序数组中，将数组一分为二，将要查询的元素和分割点进行比较，分为三种情况</p>
<ul>
<li>相等直接返回</li>
<li>元素大于分割点，在分割点右侧继续查找</li>
<li>元素小于分割点，在分割点左侧继续查找</li>
</ul>
<p>时间复杂： <strong>O(lgn)</strong>.</p>
<h4>要求</h4>
<ul>
<li>必须是有序的数组，并能支持随机访问</li>
</ul>
<h4>变形</h4>
<ul>
<li>查找第一个值等于给定的
<ul>
<li>在相等的时候做处理，向前查</li>
</ul></li>
<li>查找最后一个值等于给定的值
<ul>
<li>在相等的时候做处理，向后查</li>
</ul></li>
<li>查找第一个大于等于给定的值
<ul>
<li>判断边界减1</li>
</ul></li>
<li>查找最后一个小于等于给定的值
<ul>
<li>判断边界加1</li>
</ul></li>
</ul>
<h4>实际应用</h4>
<ul>
<li>用户ip区间段查询</li>
<li>
<p>用于相似度查询</p>
<p>package sort</p>
<p>import "fmt"</p>
<p>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
}</p>
<p>func main() {
arr := make([]int, 1024<em>1024, 1024</em>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("没有找到数据")
}
}</p>
</li>
</ul>