2020 算法列表查找

algorithms_rogramming.jpg

列表查找

在列表中查找指定元素。

• 输入为列表和要查找的元素
• 输出元素下标或未查找到元素

顺序查找

从列表第一个元素开始、顺序进行搜索，直到找到为止。

查找

二分查找

二分查找是有前提的、需要列表是有序的。在查找区间内开始，通过对查找值和查找区间的中间值的比较、可以使候选区减少一半。

二分查找

首先我们找到中间数 4 ，然后对比 4 和 6 大小关系，因为 6 大于 4 所以在左侧作为查找区间，找到中间值 7 后再和 6 比较 7 大于 6 所有在左侧中查找，因为现在左侧就一个元素所以就找到了 6 给出下标，否则给出 -1 表示没有找到

下面示例中我们假设列表是递增，从小到大的列表。

def binary_search(arr,val):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) //2
        if arr[mid] < val:
            low = mid + 1
        elif arr[mid] > val:
            high = mid - 1
        else:
            return mid
    return -1

这里我们初始化两个指针分布指向列表开始（左侧）和结束位置。

low = 0
high = len(arr) - 1

然后设置循环终止条件，也就是查找区间不为空

while low <= high

然后我们找到查找区间的中间位置，来得到查找区间中间值

mid = (low + high) //2

通过比较中间值和要查找的值来更新右侧（如果中间值大于要查找的值），更新左侧值（如果中间值小于要查找的值)，如果相等返回下标，如果没找到返回 -1

因为循环减半所以时间复杂度O(log n)

def bin_search_two(li,value,low,high):
    if low <= high:
        mid = (low + high) // 2
        if li[mid] == value:
            return mid
        elif li[mid] > value:
            return bin_search_two(li,value,low,mid-1)
        else:
            return bin_search_two(li,value,mid+1,high)
    else:
        return

也可以写出递归形式，看到递归大家可能就想到会不会增加时间复杂度，这里递归是尾递归和循环一样效率，这是根据你所使用语言而定，python 好像没有对尾递归进行优化。

排序稳定性

对于排序会有一些关键字相等的，

(2,a),(3,b),(1,c),(2,d)

稳定排序为关键字相同在排序后，他们之间对象位置不变，也就是以数字进行排序后 (2,a)还是排在(2,d)的前面。也就是他们之间循序没有变化。

最后希望大家关注我们微信公众号

wechat.jpeg