环球热推荐: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