有序数组查找

在一个有序数组中查找某个数字是否存在

首先看暴力解法(图片均为使用语雀画出)

public static int find(int[] array, int aim) {
    for (int i = 0; i < array.length; i++) {
        if (aim == array[i]) {
            return i;
        }
    }
    return -1;
}

二分查找

public static int find(int[] array, int aim) {
    // 初始化left = 最左侧, right = 最右侧
    int left = 0;
    int right = array.length - 1;

    // 当left > right则表示遍历完成
    while (left <= right) {
        // 获取中间的值
        int middle = (left + right) / 2;
        int middleValue = array[middle];
        if (middleValue == aim) {
            // 已经找到目标
            return middle;
        } else if (middleValue < aim) {
            // 目标在middle的右侧，重置left
            left = middle + 1;
        } else {
            // 目标在middle的左侧，重置right
            right = middle - 1;
        }
    }
    return -1;
}

时间复杂度明显减少

查找数组中重复的数字

假设给定一个数字数组里面的数字介于0~10之间,找出重复的数字

设置一个新的数组长度为11用于表示0~10这些数字是否存在数组中,存在一次相应的值+1.如图

数组中2,3,4存在则exists数组索引值为2,3,4的值由空变成1,所以要是出现重复的数字,则值>=1表示重复,根据上述思路完善代码

public static ArrayList<Integer> repeat(int[] array) {
    //设置动态数组更好处理结果
    ArrayList<Integer> result = new ArrayList<>();
    int[] exists = new int[11];
    for (int i = 0; i < array.length; i++) {
        int value = array[i];
        // 当前位置已经为1了表示重复所以加入结果数组中
        if (exists[value] == 1) {
            result.add(value);
        }
        // 用exists标示记录,每次出现值+1
        exists[value]++;
    }
    return result;
}