耐心和持久胜过激烈和狂热。
哈喽大家好，我是陈明勇，本文分享的内容使用 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)，基于区间特点的不同（左闭右闭、左闭右开），二分查找算法的写法也不同。
