查找算法-顺序查找和折半查找

顺序查找

遍历数组的每一个元素，线性查找，时间复杂度为O(n).

代码

class Solution:
    def GetNumberOfK(self, data, k):
        length=0
        for i in range(len(data)):
            if data[i]==k:
                return k
        return -1

折半查找（二分查找）

说明：元素必须是有序的，如果是无序的则要先进行排序操作。
基本思想：也称为是折半查找，属于有序查找算法。用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。

注：折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。——《大话数据结构》

复杂度分析：最坏情况下，关键词比较次数为log2(n+1)，且期望时间复杂度为O(log2n)；

循环（python）

def test(target,array):
    low=0
    high=len(array)-1
    flag=False
    while low<=high:
        k=int((high-low)/2)+low
        if array[k]==target:
            return target
        if array[k]<target:
            low=k+1
        if array[k]>target:
            high=k-1
    return -1
a=[1,2,3,4,5]
test(8,a)

递归：

def test(target,array):

    low=0
    high=len(array)-1
    def GetNumberOfK(target,array,low,high):
        if low>high:
            return -1
        k=int((high-low)/2)+low
        print(k)
        if array[k]==target:
            return target
        if array[k]<target:
            return GetNumberOfK(target,array,k+1,high)
        if array[k]>target:
            return GetNumberOfK(target,array,low,k-1)
    return GetNumberOfK(target,array,low,high)
a=[1,2,3,4,5]
test(8,a)

另外针对二分查找的优化算法，包括插值查找：

• （mid=low+(key-a[low])/(a[high]-a[low])*(high-low)）

• 对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。

• 复杂度分析：查找成功或者失败的时间复杂度均为O(log2(log2n))

及斐波切纳查找法。
详细见：七大查找算法：https://www.cnblogs.com/soul-stone/p/8051695.html