查找算法总结

       数据结构中经常用到查找算法，所谓查找，就是 在一个已知无(或有序）序队列中找出与给定关键字相同的数的具体位置。常用的查找算法有五中：顺序查找、二分查找（折半查找）、二叉排序树查找、哈希表法、分块查找。五中查找算法各有各的优点和缺点，在这篇博客中，我就介绍下各种查找方法的优缺点、局限性以及代码实现方式。

      一、顺序查找算法

     原理是让关键字与队列中的数从第一个开始逐个比较，直到找出与给定关键字相同的数为止，它的缺点是效率低下。时间复杂度为O(n)，这种方式一般刚接触编程的人会用到，因为效率低下，在生产环境上很少使用的。实现代码如下：

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

       二、二分（折半）查找算法

        二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。此查找算法的时间复杂度为o（log（n））。

        假如有队列：10，20，30，40，50，60，70，从中查找出60所在的位置，那么

         1、获取该队列的中间数据，40，与60所比较，发现不等且目标值>中间值

         2、在50，60，70中查找，取中间值60，发现与目标值相等，返回该数据所在位置，查询结束

          代码实现如下：

public static int binarySearch(Integer[] srcArray, int des) {
        int low = 0;
        int high = srcArray.length - 1;
        while ((low <= high) && (high <= srcArray.length - 1)) {
            // 获取中间位置
            int middle = low + ((high - low) >> 1);
            // 如果与中间位置数据相等，查找结束，返回结果
            if (des == srcArray[middle]) {
                return middle;
                // 目标值小于中间位置数据，说明目标值在前一半队列中，下一循环在前一半列表中查询
            } else if (des < srcArray[middle]) {
                high = middle - 1;
            } else {
                // 目标值大于中间位置数据，说明目标值在后一半队列中，下一循环在后一半列表中查询
                low = middle + 1;
            }
        }
        return -1;
    }