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

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

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

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

分为：顺序查找。

折半查找。

查找有两种形态：

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

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

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

顺序查找：

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

1. usingSystem;
2. usingSystem.Collections.Generic;
3. usingSystem.Linq;
4. usingSystem.Text;
5.  
6. namespaceSequential
7. {
8. classProgram
9. {
10. staticvoidMain(string[]args)
11. {
12. Listlist=newList(){2,3,5,8,7};
13.  
14. varresult=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. staticintSequenceSearch(Listlist,intkey)
26. {
27. for(inti=0;i<>
28. {
30. //查找成功，返回序列号
31. if(key==list[i])
32. returni;
33. }
34. //未能查找，返回-1
35. return-1;
36. }
37. }
38. }
    

    

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

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

    那结果是相当的啊。

    不过要注意，这种查找有两个缺点：

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

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

    上代码:

    1. usingSystem;
    2. usingSystem.Collections.Generic;
    3. usingSystem.Linq;
    4. usingSystem.Text;
    5.  
    6. namespaceBinarySearch
    7. {
    8. classProgram
    9. {
    10. staticvoidMain(string[]args)
    11. {
    12. Listlist=newList(){3,7,9,10,11,24,45,66,77};
    13.  
    14. varresult=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. ///
        ///折半查找

        ///
    25. ///
    26. ///
    27. publicstaticintBinarySearch(Listlist,intkey)
    28. {
    29. //最低线
    30. intlow=0;
    31.  
    32. //最高线
    33. inthigh=list.Count-1;
    34.  
    35. while(low<=high)
    36. {
    37. //取中间值
    38. varmiddle=(low+high)/2;
    39.  
    40. if(list[middle]==key)
    41. {
    42. returnmiddle;
    43. }
    44. else
    45. if(list[middle]>key)
    46. {
    47. //下降一半
    48. high=middle-1;
    49. }
    50. else
    51. {
    52. //上升一半
    53. low=middle+1;
    54. }
    55. }
    56. //未找到
    57. return-1;
    58. }
    59. }
    60. }
        

        

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

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

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

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

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

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