数组元素查找-蒲公英云

数组元素查找

小鱼儿 2023-05-30 09:18 124阅读 0赞

线性查找（乱序/有序):

public class FunctionTestUnit {
public static void main(String[] args) {
    int[] arr = new int[20];
    //向数组内输入一组随机数
    Random rd = new Random();
    for (int i = 0; i < arr.length; i++) {
        arr[i] = rd.nextInt(100);
    }
    System.out.println(Arrays.toString(arr));
    //给数组排序
    Arrays.sort(arr);
    System.out.println(Arrays.toString(arr));
    // 数组元素的查找，找到指定元素，返回其下标，找不到返回-1
    // 线性查找
    int index = -1;
    //写一个函数来实现数组中元素的查找,用Alt  + Enter 来快速创建
    index = linearSearch(arr, 21);
    System.out.println(index);
    }
    /**
 * 线性查找 花费的时间 - 线性时间
 * @param arr
 * @param i
 * @return
 */
private static int linearSearch(int[] arr, int i) {
    for (int j = 0; j < arr.length; j++) {
        if(arr[j] == i){
            return j;
        }
    }
    return -1;
}
}

二分查找（有序）：

非递归：

public class 二分查找非递归 {
    public static void main(String[] args) {
    int[] arr = new int[11];
    Random rd = new Random();
    for (int i = 0; i < arr.length; i++) {
        arr[i] = rd.nextInt(100);
    }
    Arrays.sort(arr);
    // arr[index] : O(1)常量时间
    // 乱序/有序  1.线性查找 O(n)  有序数组查找: 二分查找 O(logn)
    int index = binarySearch(arr, 45);
    System.out.println("index:" + index);
    System.out.println(Arrays.toString(arr));
}
/**
 * 
 * @param arr
 * @param i
 * @return
 */
private static int binarySearch(int[] arr, int i) {
    int low = 0, high = arr.length - 1;
    int mid = -1;
    while (low <= high) {
        mid = (low + high) / 2;
        if (arr[mid] == i) {
            return mid;
        } else if (arr[mid] < i) {
            low = mid + 1;
        } else if (arr[mid] > i) {
            high = mid - 1;
        }
    }
    return -1;
}
}

递归：

public class 二分查找递归 {
    public static void main(String[] args) {
    int[] arr = new int[11];
    Random rd = new Random();
    for (int i = 0; i < arr.length; i++) {
        arr[i] = rd.nextInt(100);
    }
    Arrays.sort(arr);
    // arr[index] : O(1)常量时间
    // 乱序/有序  1.线性查找 O(n)  有序数组查找: 二分查找 O(logn)
    int index = binarySearch(arr, 45);
    System.out.println("index:" + index);
    System.out.println(Arrays.toString(arr));
}
//自己调用自己
private static int binarySearch(int[] arr, int data) {
    return binarySearch(arr, 0, arr.length - 1, data);
}
// if(递归结束的关系){
//}else{
//规模之间的递推关系
//}
/**
 * 
 * @param arr
 * @param i
 * @param j
 * @param data
 * @return
 */
private static int binarySearch(int[] arr, int i, int j, int data) {
    if (i > j) { // 递归结束的条件，表示data值不存在
        return -1;
    }
    int mid = (i + j) / 2;
    if (arr[mid] == data) { // 当前递归结束的条件
        return mid;
    }
    if (arr[mid] > data) { // i <-> mid-1
        return binarySearch(arr, i, mid - 1, data);
    } else { // mid+1 <-> j
        return binarySearch(arr, mid + 1, j, data);
    }
}
}