查找算法太复杂?别慌,看看就会了

举报
宇宙之一粟 发表于 2022/01/15 00:36:26 2022/01/15
【摘要】 查找算法 在LeetCode刷题或者面试过程中发现,查找问题一直是不可避免的。对任何数据结构的遍历过程无非就是查找过程。 我们需要针对某些数据结构的特点如何正确地、高效地进行查找,而查找的过程最需要注...

查找算法

在LeetCode刷题或者面试过程中发现,查找问题一直是不可避免的。对任何数据结构的遍历过程无非就是查找过程。

我们需要针对某些数据结构的特点如何正确地、高效地进行查找,而查找的过程最需要注意边界控制。

下面以二分查找为例。

1. 二分查找★★☆

目的:在一个含有N个元素的有序数组中有效地的定位目标值。

思想:假设在有序数组arr中查找元素k,返回k所在的下标(索引值)。设arr[low,high]是当前的查找区间,确定该区间的中间位置 m i d = ⌊ ( l o w + h i g h ) / / 2 ⌋ mid=⌊(low+high)//2⌋ mid=(low+high)//2,然后将待查的k值与arr[mid]比较:

  • k==arr[mid],说明找到k,则查找成功并且终止。
  • k<arr[mid],根据数组有序的前提,目标值k在左边的区域中,索引的范围改为[low, mid-1]
  • k>arr[mid],目标值在右边的区域中,查找索引范围改为[mid+1, high]。

时间复杂度: O ( l o g 2 n ) O(log_2n) O(log2n)

代码实现

# -*- coding: utf-8 -*-
# @Time      : 2020-04-11 23:28
# @Author    : yuzhou_1su
# @ContactMe : https://blog.csdn.net/yuzhou_1shu
# @File      : Binary_Search.py
# @Software  : PyCharm


def binary_search1(arr, item):
    """
    二分查找的非递归实现1

    :param arr: 有序数组
    :param item: 待查元素
    :return: 找到待查元素的所有;如果找不到,则返回None
    """
    low = 0
    high = len(arr) - 1  # 注意此处,high索引能取到

    while low <= high:  # 条件是low<=high,区间中没有元素时结束
        mid = (low + high) // 2
        curr_item = arr[mid]

        if curr_item == item:
            return mid
        elif item < curr_item:
            high = mid - 1  # high = mid - 1
        else:
            low = mid + 1
    return None


def binary_search2(arr, item):
    """
    左边界为n的二分查找

    :param arr: 给定一个有序数组
    :param item: 待查找的元素
    :return: 找到待查元素的所有;如果找不到,则返回None
    """
    
    low = 0
    high = len(arr)  # 此处 high的索引不能取到
    while low < high:  # 条件是low<high,区间中有一个元素时也结束
        mid = (low + high) // 2
        if arr[mid] == item:
            return mid
        elif item < arr[mid]:
            high = mid  # high = mid
        else:
            low = mid + 1
    
    return None


def binary_search3_by_recursion(arr, item, low, high):
    """
    二分查找的递归实现
    :param arr: 给定一个有序数组
    :param item: 待查找的元素
    :param low: 左边界
    :param high: 右边界
    :return: 找到待查元素的所有;如果找不到,则返回None
    """

    # 递归终止条件
    if low > high:
        return None
    mid = low + (high - low) // 2
    if arr[mid] == item:
        return mid
    elif arr[mid] > item:
        return binary_search3_by_recursion(arr, item, low, mid-1)
    else:
        return binary_search3_by_recursion(arr, item, mid+1, high)

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75

二分查找边界问题探讨:二分查找有几种写法?

2. 顺序查找★☆☆

如果数组无序的话,只能通过循环遍历进行查找。

时间复杂度: O ( n ) O(n) O(n)

# -*- coding: utf-8 -*-
# @Time      : 2020-09-09 18:06
# @Author    : yuzhou_1su
# @ContactMe : https://blog.csdn.net/yuzhou_1shu
# @File      : linear_search.py
# @Software  : PyCharm


def linear_search(sequence, target):
    """线性查找
    :param sequence: 待查找序列,可以无序
    :param target: 待查元素
    :return: 找到待查元素的所有;如果找不到,则返回None
    """

    for i, v in enumerate(sequence):
        if v == target:
            return i
    return None


  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

3. 索引查找

增加一个索引表,索引表的每一项称为索引项,索引项的一般形式: (Key, Value)

索引查找的过程是:先在索引表中快速查找(索引表中可以按关键字有序排序,例如采用二分查找),找到关键字,然后通过对应的地址找到主数据表中的元素。

分块查找是一种典型的索引查找,其性能介于顺序查找和二分查找之间。

文章来源: blog.csdn.net,作者:宇宙之一粟,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/yuzhou_1shu/article/details/109263684

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

举报
请填写举报理由
0/200