快捷導航

詳解Go語言實現(xiàn)線性查找算法和二分查找算法

更新時間：2022年12月20日 08:15:05 作者：陳明勇

線性查找又稱順序查找，它是查找算法中最簡單的一種。二分查找，也稱折半查找，相比于線性查找，它是一種效率較高的算法。本文將用Go語言實現(xiàn)這兩個查找算法，需要的可以了解一下

線性查找

線性查找又稱順序查找，它是查找算法中最簡單的一種。它的基本思想是在在一組數(shù)據(jù)中，從第一個元素開始，依次和預期值比較，直到和預期值相等，則查找成功，如果所有元素都比較過，沒找到與預期值相等的元素，則查找失敗。

算法

func LinearSearch(nums []int, target int) int {
    for i, num := range nums {
        if num == target {
            return i
        }
    }
    return -1
}

算法很簡單，遍歷 nums 切片，然后依次比較，找到與 target 相等的元素則返回該元素在切片中的下標值，否則返回 -1，表示沒有找到與 target 相等的元素。

該算法的時間復雜度為 O(N)?？梢园l(fā)現(xiàn)，如果切片里有很多元素，然后要查找到元素處于最后一個位置，或者根本就沒有要查找的元素，算法將遍歷一整個切片，這種查找效率很低。

二分查找

二分查找，也稱折半查找，相比于線性查找，它是一種效率較高的算法，但是二分查找要求數(shù)組或切片中的元素必須是有序存儲的。時間復雜度為 O(logn)。圖解：

nums = [1, 2, 3, 4, 5]

劃定左邊界 left 和右邊界 right，初始值分別為 0 ，數(shù)組長度 - 1 = 5 - 1 = 4
遍歷數(shù)組 nums，取區(qū)間的中間位置 mid = left + (right - left) / 2 = 2，使用這個公式而不是 [ (left + right) / 2] 是防止 left + right 之后的值溢出。
比較數(shù)值，如果中間值 nums[mid] 與目標值 target 相等，則結(jié)束查找
如果中間值 nums[mid] 大于目標值 target，說明要尋找的值可能在左邊的區(qū)間，移動右邊界的位置，往坐區(qū)間尋找。
如果中間值 nums[mid] 小于目標值 target，說明要尋找的值可能在右邊的區(qū)間，移動左邊界的位置，往坐區(qū)間尋找。
重復以上查找的操作，直到找到元素，或遍歷結(jié)束。

算法

func BinarySearch(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] == target {
            return mid
        } else if nums[mid] > target {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return -1
}

上述代碼是基于區(qū)間【左閉右閉】的特點去編寫的，左閉右閉就是區(qū)間涵蓋左邊界的元素和右邊界的元素。

【左閉右閉】這個特點會影響 for 循環(huán) 的條件 → left <= right，因為區(qū)間包含右元素，因此left 等于 right 是有意義的。

除此之外，左閉右閉的特點還會影響 left 和 right 的值，初始值為 0，和 len - 1。因為 mid 的值已經(jīng)比較過了，基于左閉右閉的特點，left 下次的值應(yīng)為 mid + 1，而 right 下次的值應(yīng)為 mid - 1，不能為 mid。

總之，左閉右閉的特點，影響著循環(huán)條件，和 left 與 right 的值。

初始值 left = 0, right = len - 1
循環(huán)條件 left <= right
后續(xù)值 left = mid + 1，right = mid -1

【左閉右開】的算法：

func BinarySearch(nums []int, target int) int {
    left, right := 0, len(nums)
    for left < right {
        mid := left + (right-left)/2
        if nums[mid] == target {
            return mid
        } else if nums[mid] > target {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return -1
}

左開右閉，涵蓋左邊的元素，不包含右邊的元素，因此 left = 0，我們要取到數(shù)組的最后一個元素，right 的值取不到，因此 right = len，這樣就能取到 len - 1 的值了。

循環(huán)條件，left < right，沒有等于號，因為 right 取不到，等于的話是沒有意義的。

由于 mid 已經(jīng)比較過了，后續(xù) left 的值為 mid + 1，right 的值為 mid。

總結(jié)