学习回顾算法（二分法查找）

ゞ浴缸里的玫瑰 2022-06-04 04:12 230阅读 0赞

## 二分法查找概述 ##

二分法查找也称为折半查找，属于有序查找算法。用给定值key先和中间结点的关键字比较，中间结点把线形表分成两个字表，若相等则查找成功；若不相等，再根据key与该中间结点关键字的比较结果确定下一步查找哪个字表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。

**前提条件**  
列表中元素必须是有序的，如果是无须的则需要进行排序操作。

**二分查找示例**  
假如有一组数为1,3,5,7,9,11,13,15要查找给定值5。设三个变量front、mid、end分别指向数据的上界、中界和下界，mid=(front+end)/2  
1、开始领front=0(指向1），end=7（指向15），则mid=3（指向7）。因为mid>key，故应在前半段中查找。  
2、新的end=mid-1=2，而front=0不变，则新的mid=1（指向3）。此时key>mid。故确定应在后半段中查找。  
3、新fron=mid+1=2，而end=2不变，则新的mid=2,这是key=mid，查找成功。

## 二分法查找算法分析 ##

时间复杂度：  
1、最坏取款查找最后一个元素：T(n) = O(logn)  
2、最好的情况，就是要查找的元素在中间。O(1)1，

## 二分法查找算法实现 ##

**1、golang实现**

package main
    
    import (
        "fmt"
    )
    
    func BinarySearch(values []int, key int) int {
        if len(values) == 0 {
            return -1
        }
        front := 0
        end := len(values) - 1
        mid := (front + end) / 2
    
        for front < end && values[mid] != key {
            if values[mid] > key {
                end = mid - 1
            } else {
                front = mid + 1
            }
            mid = (front + end) / 2
        }
    
        if values[mid] == key {
            return mid
        }
    
        return -1
    }
    
    func main() {
    
        values := []int{
       1, 3, 5, 7, 9, 11, 13, 15}
        fmt.Println(values)
        index := BinarySearch(values, 5)
        fmt.Println(index)
        index = BinarySearch(values, 100)
        fmt.Println(index)
        return
    }

结果：

[1 3 5 7 9 11 13 15]
    2
    -1