二分查找
===
> 有一天阿,大傻和小紅在玩游戲,小紅在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 防止死循環
