二分查找和顺序查找-向日葵屋

二分查找和顺序查找

た入场券 2022-11-12 02:51 316阅读 0赞

顺序查找可以处理有序数组，也可以处理无序数组，依次遍历数组，查找待找元素，其时间复杂度为o(n)；折半查找只能处理有序数组，每次查找的过程中，都会将查找范围缩小一半，其时间复杂度为o(log2n)，以2为底，n的对数。

顺序查找

顺序查找即按照数组的元素下标位置，依次去比对查找，直到找到该元素为止，若循环结束依然未找到该元素，说明数组中没有带查关键字。顺序查找时，理论上最多查找n次，顺序查找的时间复杂度为o(n)。

例如，数组array，有元素{2，3，4，5，6，7，8，9，10}，如果要找到元素7在数组中为止，须要遍历6次

代码实现

public class SerialSearch {
    public static void main(String[] args) {
        int[] array = {2, 3, 4, 5, 6, 7, 8, 9, 10};
        System.out.println(serialSearch(array, 4));
    }
    /**
     * @顺序查找
     * @param arr 数组
     * @param key 待查找元素
     * @return
     */
    public static int serialSearch(int[] arr, int key) {
        for (int i=0; i<arr.length; i++) {
            if (arr[i] == key) {
                return i;
            }
        }
        return -1;
    }
}

二分查找

二分查找法又叫做折半查找，要求待查找的序列有序，每次查找都取中间位置的值与关键字进行比较，如果中间位置的值比待查关键字大，则在序列的左半部分继续执行该过程，如果中间位置的值比待查关键字小，则在序列的右半部分继续执行该查找过程，直到找到关键字为止，否则在序列中没有待查关键字。二分查找一直在折半，最终的时间复杂度为o(log2n)，以2为底，n的对数

同样，数组array，有元素{2，3，4，5，6，7，8，9，10}，如果要找到元素7在数组中位置，查找3次即可达到

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hZ2kxMjAx_size_16_color_FFFFFF_t_70

代码实现

public class BinarySearch {
    public static void main(String[] args) {
        int[] array = {2,3,4,5,6,7,8,9,10};
        System.out.println(binarySearch(array, 7));
    }
    /**
     * @二分查找法
     * @param arr 数组
     * @param key 待查找元素
     * @return
     */
    public static int binarySearch(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;
        int mid;
        while (low <= high) {
            mid = (high-low)/2+low; // 中间位置
            if (arr[mid] == key) {
                return mid;
            } else if (key > arr[mid]) { // 向右查找
                low = mid+1;
            } else { // 向左查找
                high = mid-1;
            }
        }
        return -1;
    }
}