算法（二）之查找技术 —— 二分查找（BinarySearch）和顺序查找(SeqSearch)

顺序查找是非常简单常用的查找算法，基本思路：从第一个元素m开始逐个与需要查找的元素x进行比较，当比较到元素值相同(即m=x)时返回元素m的下标，如果比较到最后都没有找到，则返回-1。该算法的时间复杂度为O(n)，如果数据量很大时查找效率会很低。

顺序查找也是蛮力法的一种体现，就是一个个的去比较，直到要找到我要找的数据为止。

直接上代码：

 public static int seqSearch(int[] array,int des){
    for(int i=0;i<array.length;i++){
        if(array[i]==des){
            return i;
        }
    }
    return -1;
}

二分查找（又称为折半查找）是在有序序列中查找比较多的查找算法，基本思路：设有一个从小到大的序列，取中间的元素m进行比较，如果等于需要查找的元素x则返回元素m的下标，若x大于m则再从右边的区间查找，若x小于m则再从左边的区间查找，这样每次减少一半的查找范围。时间复杂度为O(lgn)，查找速度相对顺序查找要快很多，但是查找的数据序列必须是有序序列（即数据是从小到大或从大到小排序的）。

所以二分查找有个必须前提： 源数据必须是有序序列。

二分查找必须设计为左闭右开的原则，就像高数上的区间[0 ， 1），这样才会保证各个区间之间不会出现断层的现象。

//数组在fromIndex和toIndex之间有没有key这个值 并返回下标
public static int binarySearch(int[] array,int fromIndex,int toIndex,int key){
    int low = fromIndex;
    int high = toIndex -1;    //右开的体现
    while(low < high){
        int middle = (low+high)/2;  //等价于(low+high)>>>1  无符号除以2
        if(key > array[middle]){
            low = middle + 1;
        }else if(key < array[middle]){
            high = middle - 1;
        }else{
            return middle;
        }
    }
    return -1;
}

顺序查找应用场景：

（1）如果线性表中的元素是无序的，则必须使用顺序查找
（2）如果线性表中的元素是有序的，但采用的是链式存储结构，则也必须使用顺序查找

二分查找应用场景：

源数据采用的是顺序存储结构并且数据是有序序列的时候采用二分查找。（二分查找不推荐使用递归算法）