算法 之 查找算法

查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中，查找是常用的基本运算。

用关键字标识一个数据元素，查找时根据给定的某个值，在表中确定一个关键字的值等于给定值的记录或数据元素。在计算机中进行查找的方法是根据表中的记录的组织结构确定的。

二分查找

说明：元素必须是有序的，如果是无序的则要先进行排序操作。

基本思想

也称为是折半查找，属于有序查找算法。用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k值与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。

复杂度分析

最坏情况下，关键词比较次数为log₂(n+1)，且期望时间复杂度为O(log₂n)。

折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。

Java实现

public class BinarySearch {

    /**
     * 迭代法
     *
     * @param arr    有序数组（升序）
     * @param target 查询目标关键字
     * @return
     */
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (target > arr[mid]) {// 查询关键字大于比较值，重置起始游标
                left = mid + 1;
            } else {// 查询关键字大于等于比较值，重置结束游标（等于时，也要查询前面子表，以搜索是否有匹配的最左重复元素）
                right = mid;
            }
        }
        if (arr[right] == target) {
            return right;
        }
        return -1;
    }

    /**
     * 递归法
     *
     * @param arr      有序数组（升序）
     * @param low      子表起始位置
     * @param high     子表结束位置
     * @param target   查询目标关键字
     * @param hitIndex 查询关键字命中的位置（针对查找重复有序数组中最左边的target的情况设置该参数）
     * @return
     */
    private static int binarySearch(int[] arr, int low, int high, int target, int hitIndex) {

        if (low > high || target < arr[low] || target > arr[high]) {// 递归退出条件
            return hitIndex;
        }

        int mid = (low + high) / 2; // 折半

        if (target < arr[mid]) {   // 查询关键字小于比较值，查询前面子表
            return binarySearch(arr, low, mid - 1, target, hitIndex);
        }
        if (target > arr[mid]) {   // 查询关键字大于比较值，查询后面子表
            return binarySearch(arr, mid + 1, high, target, hitIndex);
        }

        // 查询关键字等于比较值时，先不退出，接着查询前面子表来查询可能匹配的最左边target
        return binarySearch(arr, low, mid - 1, target, mid);
    }

    public static void main(String[] args) {
        int[] testData = {1, 2, 3, 5, 5, 5, 8, 13, 21, 34, 55, 89};

        // 匹配最左元素情况
        System.out.println(binarySearch(testData, 0, testData.length - 1, 5, -1));
        System.out.println(binarySearch(testData, 5));

        // 无匹配元素情况
        System.out.println(binarySearch(testData, 0, testData.length - 1, 4, -1));
        System.out.println(binarySearch(testData, 0, testData.length - 1, 0, -1));
        System.out.println(binarySearch(testData, 0, testData.length - 1, 99, -1));
        System.out.println(binarySearch(testData, 4));
        System.out.println(binarySearch(testData, 0));
        System.out.println(binarySearch(testData, 99));
    }
}