# go 二分查找
## 二分查找
给定一个有序数组 [1,2,4,6,8,8,10],再给定一个target值,此处以 8 为例,一般有4个查询目标
1. 从左向右第一个大于等于target的值的下标
2. 从左向右第一个大于target的值的下标
3. 从左向右最后一个小于等于target的值的下标
4. 从左向右最后一个小target的值的下标
3 和 4 是 1 和 2 的对立面,而1 和 2本质上是同一个目标
## code
```go
package main
import "fmt"
var arrs = []int{1,2,4,6,8,8,10}
func main () {
fmt.Printf("before arr: %v\n", arrs)
up_equal := binary_search_up_equal(arrs, 8)
fmt.Printf("the index of element which first ge %d is %d\n", 8, up_equal)
up := binary_search_up(arrs, 8)
fmt.Printf("the index of element which first g %d is %d\n", 8, up)
down_equal := binary_search_down_equal(arrs, 8)
fmt.Printf("the index of element which first le %d is %d\n", 8, down_equal)
down := binary_search_down(arrs, 8)
fmt.Printf("the index of element which first l %d is %d\n", 8, down)
}
// 第一个大于等于 8
func binary_search_up_equal(arrs []int, target int) int {
l, r := 0, len(arrs) - 1
for l < r {
mid := (l+r) / 2
if arrs[mid] < target {
l = mid + 1
} else {
r = mid
}
}
return l
}
// 第一个大于 8
func binary_search_up(arrs []int, target int) int {
l, r := 0, len(arrs) - 1
for l < r {
mid := (l+r) / 2
if arrs[mid] <= target {
l = mid + 1
} else {
r = mid
}
}
return l
}
// 最后一个小于等于 8
func binary_search_down_equal(arrs []int, target int) int {
l, r := 0, len(arrs) - 1
for l < r {
mid := (l+r+1) / 2
if arrs[mid] > target {
r = mid - 1
} else {
l = mid
}
}
return l
}
// 最后一个小于 8
func binary_search_down(arrs []int, target int) int {
l, r := 0, len(arrs) - 1
for l < r {
mid := (l+r+1) / 2
if arrs[mid] >= target {
r = mid - 1
} else {
l = mid
}
}
return l
}
```
## 返回值
* before arr: [1 2 4 6 8 8 10]
* the index of element which first ge 8 is 4
* the index of element which first g 8 is 6
* the index of element which first le 8 is 5
* the index of element which first l 8 is 3
有疑问加站长微信联系(非本文作者))