環球熱推薦:Go 實現線性查找算法和二分查找算法

2022-12-20 10:22:55 來源:51CTO博客


【資料圖】

耐心和持久勝過激烈和狂熱。

哈嘍大家好,我是陳明勇,今天分享的內容使用 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),基于區間特點的不同(左閉右閉、左閉右開),二分查找算法的寫法也不同。

標簽: 線性查找 時間復雜度 中間位置

上一篇:基于PowerBuilder開發的圖書管理系統
下一篇:微動態丨#yyds干貨盤點#配置 dev-server