二分查找
===
> 有一天阿,大傻和小红在玩游戏,小红在1~100内选一个数让大傻猜小红选的是哪一个数,
> 大傻就从1-100说出来,
大傻的时间复杂度是多少呢?
时间复杂度:O(n)
> 小红说大傻傻,猜了 66次才中,大傻不服气,这次大傻选一个数,让小红来猜
> 小红向猜100的一半,50大了,在猜.25大了,
用了4次就猜到了
这个就是二分查找
### 二分法
### 算法步骤
给定一个数组A,目标值T,查找T在A中位置
数组长度为n
1. 令L为0,R为n-1
2. 如果L>R,则搜索以失败告终
3. 令m(中间值元素)为"(L+R)/2"
4. 如果Am < T ,令L为m +1并回到步骤2
5. 如果Am>T,令m -1 并会步骤二
6. 但Am =T ,搜索结束,返回值m
~~~
func TestErF(t *testing.T) {
go func() {
// 模拟小红选的数
hong := rand.Intn(101)
fmt.Println("hong:",hong)
datas := make([]int,0)
for i:=0;i<=100;i++ {
datas = append(datas,i)
}
len := len(datas)
fmt.Println(len)
start := 0
end := len - 1
for start<end{
// 中间数
ms := (start + end)/2
fmt.Println("")
if datas[ms] == hong {
fmt.Printf("找到了hong:%d len:%d data:%d\n",hong,ms,datas[ms])
break
}else if datas[ms] > hong {
end = datas[ms]
continue
}else if datas[ms] < hong {
start = datas[ms]
continue
}
}
}()
time.Sleep(time.Second)
}
~~~
### 先觉条件:有序数组
### 注意 start = mid + 1 和end = mid -1 防止死循环
