当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

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

发表于: 2012-09-21   作者:128kj   来源:转载   浏览:
摘要: 网上看到《五大经典查找》,学习了。原文代码用C#,这里用java,顺便对照一下两种语言的语法。   在我们的生活中,无处不存在着查找,比如找一下班里哪个mm最pl,猜一猜mm的芳龄....... 对的这些都是查找。 在我们的算法中,有一种叫做线性查找。 分为:顺序查找。       折半查找。 查找有两种形
网上看到《五大经典查找》,学习了。原文代码用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);

下载源码:

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

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
今天就聊聊这个”五大经典查找“中的最后一个”二叉排序树“,又叫二叉查找树。 1. 概念 如图就是一
/*********************************************************************** 五大经典查找(5):利
在我们的生活中,无处不存在着查找,比如找一下班里哪个mm最pl,猜一猜mm的芳龄....... 对的这些都
大家是否感觉到,树在数据结构中大行其道,什么领域都要沾一沾,碰一碰。 就拿我们前几天学过的排序
大家可否知道,其实查找中有一种O(1)的查找,即所谓的秒杀。 哈希查找: 对的,他就是哈希查找,说到
在我们的生活中,无处不存在着查找,比如找一下班里哪个mm最pl,猜一猜mm的芳龄.......对的这些都是
原文: 算法系列15天速成——第五天 五大经典查找【中】 大家可否知道,其实查找中有一种O(1)的查找,
大家可否知道,其实查找中有一种O(1)的查找,即所谓的秒杀。 哈希查找: 对的,他就是哈希查找,说
大家可否知道,其实查找中有一种O(1)的查找,即所谓的秒杀。 哈希查找: 对的,他就是哈希查找,说
在我们的生活中,无处不存在着查找,比如找一下班里哪个mm最pl,猜一猜mm的芳龄....... 对的这些都
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号