在我们的算法中,有一种叫做线性查找。
分为:顺序查找。
折半查找。
查找有两种形态:
分为:破坏性查找, 比如有一群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);
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
更新日志
- [7504]ReferenceSoundEdition-GreatGuitarTunes(2013)[GermanyHQCD]
- 刘嘉佳《往日时光HQ》头版限量[低速原抓WAV+CUE]
- 单依纯《纯情歌》开盘母带[低速原抓WAV+CUE]
- 杨乐婷《遥望HQ》头版限量编号[低速原抓WAV+CUE]
- 蔡琴《三十周年纪念版》6N纯银镀膜[正版CD低速原抓WAV+CUE][519M]
- 张学友《昨夜梦魂中》[FLAC][453M]
- 群星《17号音乐仓库2 第9期》[320K/MP3][150.23MB]
- 汤兰花.2000-一代佳人(环球唱片金曲系列风华再现)【WAV+CUE】
- 罗美玲.2005-生日领悟(EP)【华研国际】【WAV+CUE】
- 李佳薇《相反的是》WAV
- 试音碟《金指妙弹电子琴演奏》5CD[WAV]
- 【新世纪电子】Авирадж2023-ИллюзияОбмана(FLAC)
- 陈婧霏.2024-春色(EP)【有此山文化】【FLAC分轨】
- 郭富城.2000-无忌VS未来(EP)【华纳】【WAV+CUE】
- 群星.2003-追忆林振强3CD【华纳】【WAV+CUE】