详解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)，基于区间特点的不同（左闭右闭、左闭右开），二分查找算法的写法也不同。