線性查找

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

算法

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)。可以發現，如果切片里有很多元素，然后要查找到元素處于最后一個位置，或者根本就沒有要查找的元素，算法將遍歷一整個切片，這種查找效率很低。

二分查找

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

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

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

算法

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
}

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

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

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

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

• 初始值 left = 0, right = len - 1
• 循環條件 left <= right
• 后續值 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，我們要取到數組的最后一個元素，right 的值取不到，因此 right = len，這樣就能取到 len - 1 的值了。

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

由于 mid 已經比較過了，后續 left 的值為 mid + 1，right 的值為 mid。

總結

• 初始值 left = 0, right = len
• 循環條件 left < right
• 后續值 left = mid + 1，right = mid

小結

本文對線性查找算法和二分查找算法進行了介紹。線性查找算法雖簡單，但是查找效率低，時間復雜度為 O(N)；而二分查找法效率雖較高，但是所查找的數組必須是有序的，時間復雜度為 O(logn)，基于區間特點的不同（左閉右閉、左閉右開），二分查找算法的寫法也不同。