算法系列第4天15天快速搜索五经[I]

我们的算法之一叫做线性搜索。分为：顺序搜索。半搜索。搜索有两种形式：破坏性搜索，比如有一群mms，我猜测他们的年龄，第一个猜测是23，这时，这个mm已经从我脑海中的mmlist中移除了。我不找23，所以这次搜索破坏了原来的结构。相反，非破坏性搜索不会破坏结构。顺序搜索：这个很简单，就是遍历数组，一个一个的比较，直到找到为止。复制代码如下：使用系统；使用系统。集合。通用；使用系统。Linq使用系统。文字；命名空间顺序{ class Program { static void Main(string[]args){ Listint list=new Listint(){ 2，3，5，8，7 }；var结果=SequenceSearch(列表，3)；如果(结果！=-1)控制台。WriteLine('3已在数组中找到，索引位置为：' result ')；否则控制台。WriteLine(‘哎哟，我找不到了！’);控制台。read()；}//查找静态int序列搜索(listint list，int key){ for(int I=0；我列举。计数；I) {//搜索成功，返回序列号if (key==list[i])返回I；}//找不到，返回-1 return-1；} } }

半搜：很有意思，就是每次都切成两半。比如‘幸运52’中的价格猜谜游戏，价格在999元以下，一分钟内可以猜中几个样品。如果所有玩家都知道半搜索，结果是相当平等的。但是需要注意的是，这种搜索有两个缺点：第一，数组必须是有序的，如果不是有序的，就必须是有序的。众所周知，最快的排序也是NLogN，所以.哎呦。其次，这种搜索仅限于线性顺序存储结构。上层代码：复制代码如下：使用系统；使用系统。集合。通用；使用系统。Linq使用系统。文字；命名空间binary search { class Program { static void Main(string[]args){ Listint list=new Listint(){ 3，7，9，10，11，24，45，66，77 }；var结果=BinarySearch(列表，45)；如果(结果！=-1)控制台。WriteLine('在数组中找到了45，索引位置为：' result ')；否则控制台。WriteLine(‘哎哟，我找不到了！’);控制台。read()；}///summary////半搜索////summary///param name=' list '/param////returns/returns public static int二分搜索法(list int list，int key){//最低行int low=0；//最高行int high=list。计数-1；而(低=高){//取中间值var middle=(低高)/2；if (list[middle]==键){ return middle} else if (list[middle]键){//向下半高=middle-1；} else {//上升一半低=中间1；} }//未找到return-1；} } }

正如我前面所说，有一种搜索形式是破坏性的，对于线性结构的数据来说，这是悲剧性的，因为每次它被破坏时，都可能导致整个数组元素向前或向后移动。所以线性结构的搜索不适合破坏性操作，那么有没有其他方法解决呢？嗯，肯定有，但是要等到第二天才能分享。Ps:线性搜索时间复杂度：O(n)；半无序(快队列活堆队列)的时间复杂度：O(NlogN)O(logN)；半序时间复杂度：O(LogN)；