
【資料圖】
耐心和持久勝過激烈和狂熱。
哈嘍大家好,我是陳明勇,今天分享的內容使用 Go 實現線性查找算法和二分查找算法。如果本文對你有幫助,不妨點個贊,如果你是 Go 語言初學者,不妨點個關注,一起成長一起進步,如果本文有錯誤的地方,歡迎指出!
線性查找又稱順序查找,它是查找算法中最簡單的一種。它的基本思想是在在一組數據中,從第一個元素開始,依次和預期值比較,直到和預期值相等,則查找成功,如果所有元素都比較過,沒找到與預期值相等的元素,則查找失敗。
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),基于區間特點的不同(左閉右閉、左閉右開),二分查找算法的寫法也不同。