右下侧的FAQ➡
会让你快捷使用本站
关闭提示
Arithmetic

Java-8.查找算法

PineappleCat · 3月7日 · 2021年 56次已读

顺序查找

复杂度分析:

查找成功时的平均查找长度为:(假设每个数据元素的概率相等) ASL = 1/n(1+2+3+…+n) = (n+1)/2 ;

当查找不成功时,需要n+1次比较,时间复杂度为O(n);

所以,顺序查找的时间复杂度为O(n)

    public static int sequenceSearch(int arr[], int key) {
        for (int i = 0; i < arr.length; i++) {
            if (key == arr[i]) {
                return i;
            }
        }
        return -1;
    }

二分查找

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

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

    public static int binarySearch(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;
        while (low <= high) {
            int mid = (low + high) >>> 1;
            if (arr[mid] > key) {
                high = mid - 1;
            } else if (arr[mid] < key) {
                low = mid + 1;
            } else {
                return arr[mid];
            }
        }
        return -1;
    }

Click here to view the copyright notice of this site(点击此处查看本站版权声明)
0 条回应