分享
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。
```
package main
import (
"fmt"
)
// 一分为2, 肯定有一半是有序的
func BinarySearchDef(data []int, key int, low int, high int) int {
if len(data) == 0 {
return -1
}
// 注意临界值
for low <= high {
mid := low + (high-low)/2
fmt.Println(mid)
fmt.Println(data[mid])
if key == data[mid] {
return mid
}
// 如果 key 比中间值小
if key < data[mid] {
if key == data[low] {
return low
}
//如果key 比中间值小,但是比 low 位置上的值大
if key > data[low] {
// 如果 key比中间值小, 比low位置上的值大, 同时 low 到 mid 之间的元素是无序的
if mid-1 >= low && data[low] >= data[mid-1] {
return BinarySearchDef(data, key, low, mid-1)
}
// 有序则反查另一半
high = mid - 1
}
if key < data[low] {
if mid-1 >= low && data[low] >= data[mid-1] {
return BinarySearchDef(data, key, low, mid-1)
}
low = mid + 1
}
}
if key > data[mid] {
if key == data[high] {
return high
}
if key > data[high] {
if mid+1 <= high && data[mid+1] >= data[high] {
return BinarySearchDef(data, key, mid+1, high)
}
// 有序则反查另一半, 因为该部分中肯定无对应的值
high = mid - 1
}
if key < data[high] {
if mid+1 <= high && data[mid+1] >= data[high] {
return BinarySearchDef(data, key, mid+1, high)
}
low = mid + 1
}
}
}
return -1
}
func main() {
data := []int{100, 102, 104, 106, 108, 110, 112, 114, 116, 118, 120, 121, 122, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
i := BinarySearchDef(data, 3, 0, len(data)-1)
fmt.Println(i)
}
```
有疑问加站长微信联系(非本文作者))
入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889
关注微信1305 次点击
上一篇:golang常见面试题
下一篇:你应该知道Go语言的几个优势
添加一条新回复
(您需要 后才能回复 没有账号 ?)
- 请尽量让自己的回复能够对别人有帮助
- 支持 Markdown 格式, **粗体**、~~删除线~~、
`单行代码` - 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
- 图片支持拖拽、截图粘贴等方式上传