详解Go语言实现线性查找算法和二分查找算法

线性查找

线性查找又称顺序查找，它是查找算法中最简单的一种。它的基本思想是在在一组数据中，从第一个元素开始，依次和预期值比较，直到和预期值相等，则查找成功，如果所有元素都比较过，没找到与预期值相等的元素，则查找失败。

算法

numstarget-1target

该算法的时间复杂度为 O(N)。可以发现，如果切片里有很多元素，然后要查找到元素处于最后一个位置，或者根本就没有要查找的元素，算法将遍历一整个切片，这种查找效率很低。

二分查找

二分查找，也称折半查找，相比于线性查找，它是一种效率较高的算法，但是二分查找要求数组或切片中的元素必须是有序存储的。时间复杂度为 O(logn)。图解：

nums

leftrightnumsmidleft(right - left)(left + right)left + rightnums[mid]targetnums[mid]targetnums[mid]target

算法

上述代码是基于区间【左闭右闭】的特点去编写的，左闭右闭就是区间涵盖左边界的元素和右边界的元素。

forleft <= rightleftright

leftrightlenmidleftmid + 1rightmid - 1mid

leftright

left = 0right = len - 1left <= rightleft = mid + 1right = mid -1 

【左闭右开】的算法：

leftrightrightlenlen - 1

leftrightright

midleftmid + 1rightmid

总结

left = 0right = lenleft < rightleft = mid + 1right = mid 

小结

本文对线性查找算法和二分查找算法进行了介绍。线性查找算法虽简单，但是查找效率低，时间复杂度为 O(N)；而二分查找法效率虽较高，但是所查找的数组必须是有序的，时间复杂度为 O(logn)，基于区间特点的不同（左闭右闭、左闭右开），二分查找算法的写法也不同。