频道栏目
首页 > 程序开发 > 软件开发 > 其他 > 正文
算法系列15天速成——第四天 五大经典查找【上】
2011-11-26 12:50:42           
收藏   我要投稿

 

 

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

 

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

分为:顺序查找。

        折半查找。

 

查找有两种形态:

分为:破坏性查找,   比如有一群mm,我猜她们的年龄,第一位猜到了是23+,此时这位mm已经从我脑海里面的mmlist中remove掉了。

                            哥不找23+的,所以此种查找破坏了原来的结构。

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

 

顺序查找:

    这种非常简单,就是过一下数组,一个一个的比,找到为止。

 1 using System;

 2 using System.Collections.Generic;

 3 using System.Linq;

 4 using System.Text;

 5

 6 namespace Sequential

 7 {

 8     class Program

 9     {

10         static void Main(string[] args)

11         {

12             List<int> list = new List<int>() { 2, 3, 5, 8, 7 };

13

14             var result = SequenceSearch(list, 3);

15

16             if (result != -1)

17                 Console.WriteLine("3 已经在数组中找到,索引位置为:" + result);

18             else

19                 Console.WriteLine("呜呜,没有找到!");

20

21             Console.Read();

22         }

23

24         //顺序查找

25         static int SequenceSearch(List<int> list, int key)

26         {

27             for (int i = 0; i < list.Count; i++)

28             {

29                 //查找成功,返回序列号

30                 if (key == list[i])

31                     return i;

32             }

33             //未能查找,返回-1

34             return -1;

35         }

36     }

37 }

 

\

 

折半查找: 这种查找很有意思,就是每次都砍掉一半,

             比如"幸运52“中的猜价格游戏,价格在999元以下,1分钟之内能猜到几样给几样,如果那些选手都知道折半查找,

             那结果是相当的啊。

          

不过要注意,这种查找有两个缺点:

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

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

 

上代码:

 1 using System;

 2 using System.Collections.Generic;

 3 using System.Linq;

 4 using System.Text;

 5

 6 namespace BinarySearch

 7 {

 8     class Program

 9     {

10         static void Main(string[] args)

11         {

12             List<int> list = new List<int>() { 3, 7, 9, 10, 11, 24, 45, 66, 77 };

13

14             var result = BinarySearch(list, 45);

15

16             if (result != -1)

17                 Console.WriteLine("45 已经在数组中找到,索引位置为:" + result);

18             else

19                 Console.WriteLine("呜呜,没有找到!");

20

21             Console.Read();

22         }

23

24         ///<summary>

25 /// 折半查找

26 ///</summary>

27 ///<param name="list"></param>

28 ///<returns></returns>

29         public static int BinarySearch(List<int> list, int key)

30         {

31             //最低线

32             int low = 0;

33

34             //最高线

35             int high = list.Count - 1;

36

37             while (low <= high)

38             {

39                 //取中间值

40                 var middle = (low + high) / 2;

41

42                 if (list[middle] == key)

43                 {

44                     return middle;

45                 }

46                 else

47                     if (list[middle] > key)

48                     {

49                         //下降一半

50                         high = middle - 1;

51                     }

52                     else

53                     {

54                         //上升一半

55                         low = middle + 1;

56                     }

57             }

58             //未找到

59             return -1;

60         }

61     }

62 }

 

\

 

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

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

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

 

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

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

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

  

 

 

作者 huangxincheng520

点击复制链接 与好友分享!回本站首页
相关TAG标签 四天 算法 经典
上一篇:算法系列15天速成——第三天 七大经典排序【下】
下一篇:算法系列15天速成——第五天 五大经典查找【中】
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站