`
128kj
  • 浏览: 600282 次
  • 来自: ...
社区版块
存档分类
最新评论

学习“五大经典查找”(1)

阅读更多
网上看到《五大经典查找》,学习了。原文代码用C#,这里用java,顺便对照一下两种语言的语法。

  在我们的生活中,无处不存在着查找,比如找一下班里哪个mm最pl,猜一猜mm的芳龄....... 对的这些都是查找。

在我们的算法中,有一种叫做线性查找。

分为:顺序查找。

      折半查找。

查找有两种形态:

分为:(1)破坏性查找
   比如有一群mm,我猜她们的年龄,第一位猜到了是23+,此时这位mm已经从我脑海里面的mmlist中remove掉了。哥不找23+的,所以此种查找破坏了原来的结构。

      (2)非破坏性查找, 这种就反之了,不破坏结构。


一、顺序查找:

    这种非常简单,就是过一下数组,一个一个的比,找到为止。
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
public class Program{  
     public static void main(String[] args){  
 //c#里可以这样啊:List<int> list = new List<int>() { 2, 3, 5, 8, 7 };  
  //目前JAVA还不行啊
        Integer a[]={2,3,5,8,7};
        List<Integer> list=Arrays.asList(a);
         int result = SequenceSearch(list, 3);  
        if (result != -1)  
        System.out.println("3 已经在数组中找到,索引位置为:" + result);  
         else  
                 System.out.println("呜呜,没有找到!");  
    
      }  
   
         //顺序查找   
    public static int SequenceSearch(List<Integer> list, int key){  
             for (int i = 0; i < list.size(); i++) {  
                 //查找成功,返回序列号   
                 if (key == list.get(i))  
                     return i;  
             }  
             //未能查找,返回-1   
             return -1;  
    }  
       
 }  


程序运行:
C:\java>java   Program
3 已经在数组中找到,索引位置为:1

二、折半查找:
   这种查找很有意思,就是每次都砍掉一半,比如"幸运52“中的猜价格游戏,价格在999元以下,1分钟之内能猜到几样给几样,如果那些选手都知道折半查找,那结果是相当的啊。
   
不过要注意,这种查找有两个缺点:

第一: 数组必须有序,不是有序就必须让其有序,大家也知道最快的排序也是NLogN的,所以.....呜呜。

第二: 这种查找只限于线性的顺序存储结构。


上代码:
import java.util.*;
public class BSearch{  
         public static void main(String[] args)  
         {  
              Integer a[]={ 3, 7, 9, 10, 11, 24, 45, 66, 77 };
              List<Integer> list=Arrays.asList(a);
           
   
             int result = BinarySearch(list, 45);  
   
             if (result != -1)  
                 System.out.println("45 已经在数组中找到,索引位置为:" + result);  
             else  
                 System.out.println("呜呜,没有找到!");  
   
             
         }  
      
   // 折半查找   
 
         public static int BinarySearch(List<Integer> list, int key)  
         {  
             //最低线   
             int low = 0;  
   
             //最高线   
             int high = list.size() - 1;  
   
             while (low <= high)  
             {  
                 //取中间值   
                 int middle = (low + high) / 2;  
   
                 if (list.get(middle) == key){  
                     return middle;  
                 } else  if (list.get(middle) > key){  
                         //下降一半   
                         high = middle - 1;  
                  }else{  
                         //上升一半   
                         low = middle + 1;  
                  }  
             }  
             //未找到   
             return -1;  
         }  
      
 }  

程序运行:
C:\java>java     BSearch
45 已经在数组中找到,索引位置为:6

   先前也说过,查找有一种形态是破坏性的,那么对于线性结构的数据来说很悲惨,因为每次破坏一下,

可能都导致数组元素的整体前移或后移。

    所以线性结构的查找不适合做破坏性操作,那么有其他的方法能解决吗?嗯,肯定有的,不过要等下一天分享。


ps:  线性查找时间复杂度:O(n);

         折半无序(用快排活堆排)的时间复杂度:O(NlogN)+O(logN);

         折半有序的时间复杂度:O(logN);

下载源码:
分享到:
评论

相关推荐

    学习“五大经典查找”(3)

    在本篇博客“学习‘五大经典查找’(3)”中,博主主要探讨了计算机科学中的查找算法,这是数据结构与算法的重要组成部分。查找算法在软件开发中起着至关重要的作用,尤其是在处理大量数据时,高效的查找算法能显著...

    算法系列15天速成 第六天 五大经典查找【下】

    由于它的有序性,可以快速定位数据,使得搜索时间复杂度降低至O(log n),在数据量大时具有明显优势。 ### 总结 掌握二叉排序树的原理及其操作是数据结构与算法学习中的一个重要里程碑。理解其动态平衡的过程和对...

    解析lookup的经典查找方式.docx

    此时,可采用经典条件查找解法,如`=LOOKUP(1, 0/(条件), 查找数组或区域)`。 **五、注意事项** - `lookup_vector`的数值必须按升序排列,否则可能得到错误结果。 - 文本不区分大小写,但逻辑值和数字区分。 - ...

    数据结构课程设计-查找

    1) 理解并实现以上五种查找算法。 2) 分析每种算法的时间复杂度和适用场景。 3) 编写程序并测试,记录运行时间,对比各算法效率。 4) 提交详细的报告,包括算法描述、设计思路、程序代码和运行结果。 二、顺序查找...

    算法系列15天速成 第四天 五大经典查找【上】

    在本篇中,我们将探讨两种经典的查找算法:顺序查找和折半查找。这两种算法在日常生活中有着广泛的应用,例如寻找班级中最漂亮的女生或猜测年龄等。 首先,我们来看顺序查找(Sequential Search)。顺序查找是最...

    C++数据结构折半查找法(二分查找)

    总的来说,二分查找法是C++数据结构学习中的一个重要部分,对于提高程序的运行效率有着重要作用。理解并能熟练运用二分查找法,将有助于提升作为程序员的数据处理能力。通过不断的实践和练习,初学者可以更好地掌握...

    第五章:查找-2021-11

    《第五章:查找》 本章内容主要涵盖了数据结构与算法中的查找技术,适用于计算机科学与技术学院的学生学习。查找是数据处理中的基础操作,它根据给定的值在数据集合中寻找相应记录或元素的过程。本章将深入探讨多种...

    C++ 二分查找法

    ### C++ 二分查找法详解 在计算机科学领域,数据结构与算法是核心课程之一,其中二分查找法(Binary Search)是一种高效的查找技术...在未来的学习和工作中,合理运用二分查找法将极大地提升数据处理的效率和准确性。

    acm折半查找法参考代码

    在ACM(国际大学生程序设计竞赛)中...总结,折半查找法是编程中的一种高效查找策略,尤其适用于处理大规模有序数据。通过熟练掌握这种算法,可以提升在ACM等编程竞赛中的竞争力,并在实际项目开发中优化数据处理性能。

    算法系列15天速成 第五天 五大经典查找【中】

    ### 知识点详解 #### 一、哈希查找简介 哈希查找是一种高效的数据查找方法,能够在平均情况下实现O(1)的时间复杂度。...通过这段代码的学习,可以帮助我们更好地理解哈希查找的工作原理及其应用场景。

    二分查找算法FLASH演示

    1. 时间复杂度低:二分查找的时间复杂度为O(log n),在大规模数据中具有显著优势。 2. 查找速度快:每次操作都能将搜索空间减半,效率高。 四、适用场景: 二分查找常用于数据库查询、字典查找、有序数据的处理等...

    数据结构实验五查找的实现.doc

    数据结构实验五主要探讨了两种查找方法的实现:线性查找和折半查找。这两种查找方法都是在数组或表中定位特定元素的关键技术,在实际编程和数据处理中有着广泛的应用。 1. 线性查找(Linear Search): 线性查找是...

    数据结构 查找

    #### 五、哈希查找 **5.1 系统简介** 哈希查找是一种高效的数据查找方法,它利用哈希函数将关键字映射到一个特定的索引位置,从而快速定位元素。 **5.2 设计思路** 哈希查找的基本步骤: 1. 选择合适的哈希函数...

    数据结构7.3树表查找

    通过这些知识点的学习,可以帮助读者更好地理解如何利用二叉排序树进行高效的查找操作。 #### 二、二叉排序树简介 二叉排序树(Binary Search Tree, BST),又称二叉查找树,是一种特殊的二叉树,具有以下性质: 1....

    搜索引擎学习 方便查找!

    #### 五、倒排索引技术详解 ##### 5.1 正向索引与倒排索引的区别 - **正向索引**:传统的索引方式,通常是基于记录ID建立索引。当进行基于字段值的搜索时,效率较高;但如果进行模糊匹配或部分词条搜索,则需要...

    数据结构-查找(1).ppt

    通过本章节的学习,我们了解了查找的基本概念、静态查找表和动态查找表的多种实现方法以及哈希表的基础知识。不同的查找方法适用于不同类型的数据结构和应用场景。选择合适的查找算法能够显著提高数据处理的效率。

    深大算法实验五——查找所有的桥

    在深大算法实验五中,主题是“查找所有的桥”,这是一个经典的图论问题,与数据结构和算法密切相关。桥在图论中指的是图中的一种特殊连接结构,如果去掉这个边,会导致原来的连通分量数量增加,即桥是维持图连通性的...

    数据结构查找教学,内含五个视频(前版).zip

    在本教学资料中,主要介绍了五种不同的查找方法,这些方法是数据结构和算法学习的基础,对于理解和优化程序性能至关重要。 首先,我们来看**顺序查找**。顺序查找是最基础的查找方法,它遍历数据序列,逐个比较元素...

    顺序表的折半查找(C语言)

    **顺序表的折半查找(C语言...这个C语言实现的折半查找程序,适用于学习数据结构和算法的学生,它有助于理解折半查找的工作原理及其在实际编程中的应用。通过实践,你可以更好地掌握C语言的内存管理和数据结构的操作。

    C#查找窗口句柄的方法

    - Pinvoke.net: 一个关于P/Invoke签名的在线数据库,可以快速查找和学习API函数的C#实现。 - CodeProject: 包含许多C#与Windows API交互的实例项目和技术文章。 总结,C#查找窗口句柄是通过调用Windows API实现的,...

Global site tag (gtag.js) - Google Analytics