二分查找:给定数组是有序的,给定一个key值。每次查找最中间的值,如果相等,就返回对应下标,如果key大于最中间的值,则在数组的右半边继续查找,如果小于,则在数组左半边查找。这种搜索算法每一次比较都使搜索范围缩小一半。最终有两种结果,一种是找到并返回下标,第二种是没找到。时间复杂度为:O(log2n)。

  • 优缺点
    优点:是比较次数少,查找速度快,平均性能好;

缺点:是要求待查表为有序表,且插入删除困难。
因此,折半查找方法适用于不经常变动而查找频繁的有序列表。

  • 算法步骤描述
    ① 首先确定整个查找区间的中间位置 mid = ( left + right )/2 。

② 用待查关键字值与中间位置的关键字值进行比较; 
若相等,则查找成功 
若大于,则在后(右)半个区域继续进行折半查找 
若小于,则在前(左)半个区域继续进行折半查找。
③ 对确定的缩小区域再按折半公式,重复上述步骤。最后,得到结果:要么查找成功, 要么查找失败。折半查找的存储结构采用一维数组存放。

  • 代码实现
/*
  Time complexity: O(logN)
*/
func BinarySearch(s []int, t int) int {
    low, high := initSearch(s)
    for low <= high {
        m := (low + high) >> 1
        if s[m] < t {
            low = m + 1
        } else if s[m] > t {
            high = m - 1
        } else {
            return m
        }
    }
    return -1
}

func initSearch(s []int) (int, int) {
    if s == nil {
        panic("Nil array")
    }
    low := 0
    high := len(s) - 1
    if high < low {
        panic("Empty array")
    }
    return low, high
}
  • 测试
func TestBinarySearch(t *testing.T) {
    array1 := []int{1, 3, 5, 7, 9, 11, 13, 15}
    target := array1[rand.Intn(len(array1))]
    fmt.Println("array: ",array1)
    fmt.Printf("search target value = %d\n",target)
    tIndex := BinarySearch(array1, target)
    fmt.Printf("target value index = %d\n", tIndex)
}
  • 结果
array:  [1 3 5 7 9 11 13 15]
search target value = 3
target value index = 1