算法系列15天速成 第四天 五大经典查找【上】
发布时间:2023-12-18 01:20:38
在我们的算法中,有一种叫做线性查找。
分为:顺序查找。
折半查找。
查找有两种形态:
分为:破坏性查找, 比如有一群mm,我猜她们的年龄,第一位猜到了是23+,此时这位mm已经从我脑海里面的mmlist中remove掉了。
哥不找23+的,所以此种查找破坏了原来的结构。
非破坏性查找, 这种就反之了,不破坏结构。
顺序查找:
这种非常简单,就是过一下数组,一个一个的比,找到为止。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Sequential
{
class Program
{
static void Main(string[] args)
{
List<int> list = new List<int>() { 2, 3, 5, 8, 7 };
var result = SequenceSearch(list, 3);
if (result != -1)
Console.WriteLine("3 已经在数组中找到,索引位置为:" + result);
else
Console.WriteLine("呜呜,没有找到!");
Console.Read();
}
//顺序查找
static int SequenceSearch(List<int> list, int key)
{
for (int i = 0; i < list.Count; i++)
{
//查找成功,返回序列号
if (key == list[i])
return i;
}
//未能查找,返回-1
return -1;
}
}
}
折半查找: 这种查找很有意思,就是每次都砍掉一半,
比如"幸运52“中的猜价格游戏,价格在999元以下,1分钟之内能猜到几样给几样,如果那些选手都知道折半查找,
那结果是相当的啊。
不过要注意,这种查找有两个缺点:
第一: 数组必须有序,不是有序就必须让其有序,大家也知道最快的排序也是NLogN的,所以.....呜呜。
第二: 这种查找只限于线性的顺序存储结构。
上代码:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace BinarySearch
{
class Program
{
static void Main(string[] args)
{
List<int> list = new List<int>() { 3, 7, 9, 10, 11, 24, 45, 66, 77 };
var result = BinarySearch(list, 45);
if (result != -1)
Console.WriteLine("45 已经在数组中找到,索引位置为:" + result);
else
Console.WriteLine("呜呜,没有找到!");
Console.Read();
}
///<summary>
/// 折半查找
///</summary>
///<param name="list"></param>
///<returns></returns>
public static int BinarySearch(List<int> list, int key)
{
//最低线
int low = 0;
//最高线
int high = list.Count - 1;
while (low <= high)
{
//取中间值
var middle = (low + high) / 2;
if (list[middle] == key)
{
return middle;
}
else
if (list[middle] > key)
{
//下降一半
high = middle - 1;
}
else
{
//上升一半
low = middle + 1;
}
}
//未找到
return -1;
}
}
}
先前也说过,查找有一种形态是破坏性的,那么对于线性结构的数据来说很悲惨,因为每次破坏一下,
可能都导致数组元素的整体前移或后移。
所以线性结构的查找不适合做破坏性操作,那么有其他的方法能解决吗?嗯,肯定有的,不过要等下一天分享。
ps: 线性查找时间复杂度:O(n);
折半无序(用快排活堆排)的时间复杂度:O(NlogN)+O(logN);
折半有序的时间复杂度:O(logN);
猜你喜欢
- 装饰器本质是一个接受参数为函数的函数。作用:为一个已经实现的方法添加额外的通用功能,比如日志记录、运行计时等。举例1.不带参数的装饰器,不用
- 具体编译过成与正常的Python源代码在x86平台上的过程无异,此篇随笔仅当用作复制黏贴的备忘录。不得不说在一个老旧系统上安装一个老旧的Py
- 目录引言 操作多线程/多进程1、创建线程池2、submit3、map4
- 前言本项目为IOT实验室人员签到考勤设计,系统实现功能:1.人员人脸识别并完成签到/签退2.考勤时间计算3.保存考勤数据为CSV格式(Exc
- 本文实例讲述了Python实现快速多线程ping的方法。分享给大家供大家参考。具体如下:#!/usr/bin/python#_*_codin
- 一 CGI.pm中的方法(routines)调用1. CGI.pm实现了两种使用方法,分别是面向对象的方式和传统的perlmodule方法的
- 一、激活函数定义激活函数 (Activation functions) 对于人工神经网络模型去学习、理解非常复杂和非线性的函数来说具有十分重
- 本文介绍了python同时替换多个字符串方法示例,分享给大家,具体如下:import rewords = ''' &
- Python3.7 基于 pycryptodome 的AES加密解密、RSA加密解密、加签验签,具体代码如下所示:#!/usr/bin/en
- 前言所谓“基础不狠,人站不稳”,对于任何一种编程语言来说基础往往都是重中之重,以Python为例,其
- 问题引入什么时候选择 T 作为参数类型,什么时候选择 *T 作为参数类型?[ ] T 是传递的指针还是值?选择 [ ] T 还是 [ ] *
- 关于 PHP 的文件操作,我们也将是通过一系列的文章来进行学习。今天我们先学习的是一个很少人使用过,甚至很多人根本不知道的扩展,它与我们日常
- 源码: 代码如下: <% '隐藏并修改文件的最后修改时间的aspshell '原理:通过FSO可以修改文件的属性,比
- 介绍godep是解决包依赖的管理工具,目前最主流的一种,原理是扫描记录版本控制的信息,并在go命令前加壳来做到依赖管理godep 建议在 g
- 当获取FileField数据时会出现编码问题在数据库里显示的是D:\python项目\wxmkczpy\uploadfile\QQ截图201
- 以a=[1,2,3] 为例,似乎使用del, remove, pop一个元素2 之后 a都是为 [1,3],如下:>>>
- 一、起源 因子分析的起源是这样的:1904年英
- 很多人觉得程序猿是高薪的代表,很多人都想学习一门编程语言,如果你想选择一种语言来入门编程,那么Python绝对是首选!其非常接近自然语言,精
- Prometheus 为开发这提供了客户端工具,用于为自己的中间件开发Exporter,对接Prometheus 。目前支持的客户端GoJa
- CONVERT将某种数据类型的表达式显式转换为另一种数据类型。由于某些需求经常用到取日期格式的不同.现以下可在SQL Server中将日期格