浅谈两个重要的搜索算法

本文涉及的产品
实时计算 Flink 版,5000CU*H 3个月
检索分析服务 Elasticsearch 版,2核4GB开发者规格 1个月
大数据开发治理平台 DataWorks,不限时长
简介: 【5月更文挑战第15天】线性搜索从数组一端按顺序遍历,直到找到目标元素,平均和最坏情况的时间复杂度均为O(N)。二分查找适用于排序数组,通过比较中间元素快速定位目标,最佳、平均和最坏情况的时间复杂度都是O(logN)。

1 两个重要的基础搜索算法

本文探讨了两种搜索算法:线性搜索和二分查找。

这里通过简单示例、代码实现和时间复杂度分析来详细讨论这两个问题。

2 线性或顺序搜索

工作原理是从一端按顺序遍历整个数组或列表,直到找到目标元素。

如果找到该元素,则返回其索引,否则返回 -1。

  • 示例:

      arr = [6, 12, 15, 11, 9, 19, 49]
    

我们需要找到 9 的索引。

实现:

        def search(nums, target):
        for i in range(len(nums)):
            if nums[i] == target:
                return i
        return -1

        if __name__ == '__main__':
            nums = [2, 12, 15, 11, 7, 19, 45]
            target = 7
            print(search(nums, target))
  • 步骤:

    1 从索引 0 开始,并将每个元素与目标进行比较。

    2 如果发现目标等于元素,则返回其索引。

    3 如果未找到目标,则返回 -1。

  • 复杂度

当目标元素是数组的第一个元素时,会出现最佳情况。在本例中,比较次数为 1。因此,时间复杂度为 。O(1)

平均情况: 平均而言,目标元素将位于数组的中间位置。在这种情况下,比较次数将为 N/2。因此,时间复杂度将是(常量被忽略) O(N)

当目标元素是数组中的最后一个元素或不在数组中时,会发生最坏的情况。在这种情况下,我们必须遍历整个数组,因此比较次数将为 N。因此,时间复杂度将是 O(N)

3 二分搜索

这种类型的搜索算法用于查找排序数组中包含的特定值的位置。二叉搜索算法遵循分而治之的原则,它被认为是最好的搜索算法,因为它运行速度更快。

现在让我们以一个排序数组为例,尝试了解它是如何工作的:

  • 示例:

              arr = [6, 12, 15, 17, 29, 39, 49]
    

假设要搜索的目标元素是 17

  • 二分查找的方法

1 将目标元素与数组的中间元素进行比较。

2 如果目标元素大于中间元素,则搜索在右半部分继续。

3 否则,如果目标元素小于中间值,则在左半部分继续搜索。

4 重复此过程,直到中间元素等于目标元素,或者目标元素不在数组中。

5 如果找到目标元素,则返回其索引,否则返回 -1。

  • 代码实现

      def search(nums, target):
          start = 0
          end = len(nums)-1
    
          is_ascending = nums[start] < nums[end]
    
          while start <= end:
              mid = start + (end-start)//2
    
              if target == nums[mid]:
                  return mid
    
              if is_ascending:
                  if target < nums[mid]:
                      end = mid-1
                  else:
                      start = mid+1
              else:
                  if target < nums[mid]:
                      start = mid+1
                  else:
                      end = mid-1
    
          return -1
    
      if __name__ == '__main__':
          nums1 = [-1, 2, 4, 6, 7, 8, 12, 15, 19, 32, 45, 67, 99]
          nums2 = [99, 67, 45, 32, 19, 15, 12, 8, 7, 6, 4, 2, -1]
          target = -1
          print(search(nums1, target))
          print(search(nums2, target))
    
  • 复杂度分析

当目标元素是数组的中间元素时,会出现最佳情况。

在本例中,比较次数为 1。因此,时间复杂度为O(1)。

平均情况:平均而言,目标元素将位于数组中的某个位置。

因此,时间复杂度将是O(logN)

当目标元素不在列表中或远离中间元素时,会发生最坏情况。
因此,时间复杂度将是O(logN)

目录
相关文章
|
1月前
|
算法 机器学习/深度学习 索引
【算法设计与分析】——搜索算法
【算法设计与分析】——搜索算法
52 1
|
1月前
|
算法 程序员 数据处理
算法与人生 揭秘C语言中高效搜索的秘诀——二分查找算法详解
算法与人生 揭秘C语言中高效搜索的秘诀——二分查找算法详解
|
2天前
|
存储 算法 Java
广度优先搜索(Breadth-First Search,BFS)是一种用于图的遍历或搜索的算法。
广度优先搜索(Breadth-First Search,BFS)是一种用于图的遍历或搜索的算法。
|
2天前
|
人工智能 算法 Java
深度优先搜索(Depth-First Search,DFS)是一种用于遍历或搜索树或图的算法。
深度优先搜索(Depth-First Search,DFS)是一种用于遍历或搜索树或图的算法。
|
5天前
|
算法 JavaScript 决策智能
基于禁忌搜索算法的TSP路径规划matlab仿真
**摘要:** 使用禁忌搜索算法解决旅行商问题(TSP),在MATLAB2022a中实现路径规划,显示优化曲线与路线图。TSP寻找最短城市访问路径,算法通过避免局部最优,利用禁忌列表不断调整顺序。关键步骤包括初始路径选择、邻域搜索、解评估、选择及禁忌列表更新。过程示意图展示搜索效果。
|
6天前
|
算法
【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值
【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值
|
6天前
|
算法
【经典LeetCode算法题目专栏分类】【第3期】回溯问题系列:单词搜索、N皇后问题、判断有效数独、解数独
【经典LeetCode算法题目专栏分类】【第3期】回溯问题系列:单词搜索、N皇后问题、判断有效数独、解数独
|
9天前
|
存储 算法 数据可视化
python多种算法对比图解实现 验证二叉树搜索树【力扣98】
python多种算法对比图解实现 验证二叉树搜索树【力扣98】
|
12天前
|
存储 算法
动态规划与搜索算法
动态规划与搜索算法
14 0
|
14天前
|
算法 Java Go
【经典算法】LeetCode 35. 搜索插入位置(Java/C/Python3/Golang实现含注释说明,Easy)
【经典算法】LeetCode 35. 搜索插入位置(Java/C/Python3/Golang实现含注释说明,Easy)
8 0

热门文章

最新文章