131 lines
2.2 KiB
Go
131 lines
2.2 KiB
Go
/*
|
|
* @Description: 二分查找
|
|
* @Version: 2.0
|
|
* @Autor: zhuyijun
|
|
* @Date: 2021-03-29 09:08:50
|
|
* @LastEditors: zhuyijun
|
|
* @LastEditTime: 2021-03-30 08:59:23
|
|
*/
|
|
package main
|
|
|
|
import "fmt"
|
|
|
|
/**
|
|
二分查找算法
|
|
*/
|
|
func BinarySearch(key int, a []int) int {
|
|
start := 0
|
|
end := len(a) - 1
|
|
for start < end {
|
|
mid := start + ((end - start) >> 1)
|
|
if key < a[mid] {
|
|
end = mid - 1
|
|
} else if key > a[mid] {
|
|
start = mid + 1
|
|
} else {
|
|
return mid
|
|
}
|
|
}
|
|
return -1
|
|
}
|
|
|
|
//查找第一个值等于给定值得元素
|
|
func BinarySearch2(nums []int, value int) int {
|
|
length := len(nums)
|
|
start := 0
|
|
end := length - 1
|
|
for start <= end {
|
|
mid := start + ((end - start) >> 1)
|
|
if nums[mid] > value {
|
|
end = mid - 1
|
|
} else if nums[mid] < value {
|
|
start = mid + 1
|
|
} else {
|
|
for mid >= 0 {
|
|
if nums[mid-1] == value {
|
|
mid--
|
|
} else {
|
|
return mid
|
|
}
|
|
}
|
|
}
|
|
}
|
|
return -1
|
|
}
|
|
|
|
// 查找最后一个值等于给定值的元素
|
|
func BinarySearch3(nums []int, value int) int {
|
|
start := 0
|
|
end := len(nums) - 1
|
|
for start <= end {
|
|
mid := start + ((end - start) >> 1)
|
|
if nums[mid] > value {
|
|
end = mid - 1
|
|
} else if nums[mid] < value {
|
|
start = mid + 1
|
|
} else {
|
|
for mid < len(nums) {
|
|
if nums[mid+1] == value {
|
|
mid++
|
|
} else {
|
|
return mid
|
|
}
|
|
}
|
|
}
|
|
}
|
|
return -1
|
|
}
|
|
|
|
// 查找第一个大于等于给定值的元素
|
|
func BinarySearch4(nums []int, value int) int {
|
|
start := 0
|
|
end := len(nums) - 1
|
|
for start <= end {
|
|
mid := (start + end) >> 1
|
|
if nums[mid] < value {
|
|
start = mid + 1
|
|
} else {
|
|
for mid >= 0 {
|
|
if nums[mid-1] >= value {
|
|
mid--
|
|
} else {
|
|
return mid
|
|
}
|
|
}
|
|
}
|
|
}
|
|
return -1
|
|
}
|
|
|
|
// 查找最后一个小于等于给定值的元素
|
|
func BinarySearch5(nums []int, value int) int {
|
|
start := 0
|
|
end := len(nums) - 1
|
|
for start <= end {
|
|
mid := (start + end) >> 1
|
|
if nums[mid] > value {
|
|
end = mid - 1
|
|
} else {
|
|
for mid < len(nums) {
|
|
if nums[mid+1] <= value {
|
|
mid++
|
|
} else {
|
|
return mid
|
|
}
|
|
}
|
|
}
|
|
}
|
|
return -1
|
|
}
|
|
|
|
func main() {
|
|
var a = []int{0, 2, 4, 7, 9, 11, 45, 67, 99, 100}
|
|
var i int = 2
|
|
key := BinarySearch(i, a)
|
|
if key > 0 {
|
|
fmt.Printf("已查到:%d,位置在:%d \n", i, key+1)
|
|
} else {
|
|
fmt.Printf("没有查到a数组中有%d", i)
|
|
}
|
|
}
|