二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。
算法时间O(log(n))
满足条件:
1.必须采用顺序存储结构。
2.必须按关键字大小有序排列。
/************************************************************
** @Description: binary_search 二分查找法
** @Author: haodaquan
** @Date: 2018-03-25 23:33
** @Last Modified by: haodaquan
** @Last Modified time: 2018-03-25 23:33
*************************************************************/
package main
import (
"fmt"
)
func main() {
a := []int{0, 1, 2, 3, 4, 5, 6}
mid := binary(a, -4)
fmt.Println(mid)
}
func binary(s []int, search int) int {
left, right, mid := 0, len(s)-1, 0
for {
if s[mid] > search {
right = mid - 1
mid = (left + right) / 2
} else if s[mid] == search {
break
} else {
left = mid + 1
mid = (left + right) / 2
}
if right < left {
mid = -1
break
}
}
return mid
}