線性查找

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

算法

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

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

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

二分查找

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

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

• 劃定左邊界 left 和右邊界 right，初始值分別為 0 ，數(shù)組長(zhǎng)度 - 1 = 5 - 1 = 4
• 遍歷數(shù)組 nums，取區(qū)間的中間位置 mid = left + (right - left) / 2 = 2，使用這個(gè)公式而不是 [ (left + right) / 2] 是防止 left + right 之后的值溢出。
• 比較數(shù)值，如果中間值 nums[mid] 與 目標(biāo)值 target 相等，則結(jié)束查找
• 如果中間值 nums[mid] 大于目標(biāo)值 target，說明要尋找的值可能在左邊的區(qū)間，移動(dòng)右邊界的位置，往坐區(qū)間尋找。
• 如果中間值 nums[mid] 小于目標(biāo)值 target，說明要尋找的值可能在右邊的區(qū)間，移動(dòng)左邊界的位置，往坐區(qū)間尋找。
• 重復(fù)以上查找的操作，直到找到元素，或遍歷結(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ū)間【左閉右閉】的特點(diǎn)去編寫的，左閉右閉就是區(qū)間涵蓋左邊界的元素和右邊界的元素。

【左閉右閉】這個(gè)特點(diǎn)會(huì)影響 for 循環(huán) 的條件 → left <= right，因?yàn)閰^(qū)間包含右元素，因此left 等于 right 是有意義的。

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

總之，左閉右閉的特點(diǎn)，影響著循環(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ù)組的最后一個(gè)元素，right 的值取不到，因此 right = len，這樣就能取到 len - 1 的值了。

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

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

總結(jié)

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

小結(jié)

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