算法 基础教程

算法 高级教程

相似性算法

original icon
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://www.knowledgedict.com/tutorial/algorithm-search.html

算法 之 查找算法


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

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

二分查找

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

基本思想

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

复杂度分析

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

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

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));
    }
}
排序算法分为两大类,一是内部排序,即数据记录在内存中进行排序,另一个是外部排序,主要是因排序的数据很大,一次不能容纳全部的排序记录,在排序过 ...
在Java中,有几种常见的快速查找算法,包括二分查找、哈希表查找以及树结构查找(如二叉搜索树)。示例代码:Maven依赖:Gradle依赖: ...
什么是算法?简而言之,任何定义明确的计算步骤都可称为算法,接受一个或一组值为输入,输出一个或一组值。 ...
###冒泡排序(BubbleSort)冒泡排序是一种简单的比较排序算法,它多次迭代列表,每次将相邻的元素进行比较并交换,直到整个列表有序。如 ...
以下是几种不同的Java异或算法实现方式,每种方式都附有详细的步骤流程、示例代码以及可能的依赖坐标。对a和b再次执行异或操作,由于此时a存储 ...