学习“五大经典查找”(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);

下载源码：