数组中的java校验号

Question

快速检查数组中整数的方法。数组中没有连续整数，而是有空间数，例如[1,4,11,120,2,3]

在时间效率方面，如何检查3 in [212,31219,1,12,4]？结果是假的

Answer 1

有两种方法

考虑大小n的数组，t搜索

线性搜索法

复杂性：O (T * N)

示例代码：

class Main {
    public static void main(String[] args) {
        int[] arr = { 212, 31219, 1, 12, 4 };
        // perform searches from here
        // for eg.
        // boolean exists = contains(arr, 4);

    }

    public static boolean contains(int[] arr, int x) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == x) {
                return true;
            }
        }
        return false;
    }
}

二进制搜索方法

复杂性：O (N * log(N) + T * log(N)

示例代码：

import java.util.Arrays;

class Main {
    public static void main(String[] args) {
        int[] arr = { 212, 31219, 1, 12, 4 };

        // sort array first => complexity O(N * log(N))
        Arrays.sort(arr);

        // perform searches from here
        // for eg.
        // boolean exists = contains(arr, 2);       
    }

    public static boolean contains(int[] arr, int key) {
        return Arrays.binarySearch(arr, key) >= 0 ? true : false;
    }
}

所以，如果你的搜索次数非常多，使用二进制搜索方法，否则使用线性搜索方法