java - 查看数组是否包含给定范围内的数字

标签 java algorithm recursion range binary-search

所以,我遇到了一个问题,要实现一个程序,如果排序后的整数数组包含大于 I 但小于 的数字,则该程序返回 true u,否则为 false

我已经确定快速排序算法是对数组进行排序的好方法,因为我不知道用户将如何输入它 - 然后,我将排序后的数组提供给二进制搜索并找出是否该数组包含指定范围内的整数。 问题是,我似乎无法对此进行推理,因为它不是我想在这里找到的一个值,而是一个范围。 另外,如果可能的话,我想递归地实现它。

这是我目前所拥有的:

import java.util.Scanner;

class RangeBinarySearch {
    public static int[] quickSort(int[] unsortedArray, int left, int right) {
    int[] sortArray = unsortedArray;
    if (left >= right)
        return sortArray;

    int pivot = unsortedArray[(left + right) / 2];

    int i = left;
    int j = right;

    while (i <= j) {
        while (unsortedArray[i] < pivot)
            i++;
        while (unsortedArray[j] > pivot)
            j--;
        if (i <= j) {
            int temp = unsortedArray[i];
            unsortedArray[i] = unsortedArray[j];
            unsortedArray[j] = temp;
            i++;
            j--;
        }
    }

    if (left < j)
        quickSort(unsortedArray, left, j);
    if (right > i)
        quickSort(unsortedArray, i, right);

    return sortArray;
    }

    public static boolean withinRangeSorted(int[] sortedArray, int I, int u) {// This uses binary search

    int start = 0;
    int end = sortedArray.length - 1;
    int mid = sortedArray[(start + end) / 2];


        if (sortedArray[start] > u || sortedArray[end] < I)
            return false;
        else if (sortedArray[start] > I && sortedArray[end] < u)
            return true;

        else {
            // What to do here? I am stuck!

        }
    return false;
    }

    public static void main(String[] args) {
    int size;
    int inum;

    Scanner input = new Scanner(System.in);
    System.out.println("Enter the size of the array: ");
    size = input.nextInt();
    int[] unsortArray = new int[size];

    for (int i = 0; i < size; i++) {
        int c = i + 1;
        System.out.println("Enter element " + c + " to be added to the array: ");
        inum = input.nextInt();
        unsortArray[i] = inum;
    }

    int left = 0;
    int right = size - 1;

    int[] sortedArray = quickSort(unsortArray, left, right);
    int I; // greater than
    int u; // less than

    System.out.println("Enter range starting point: ");
    I = input.nextInt();
    System.out.println("Enter range end point: ");
    u = input.nextInt();

    boolean result = withinRangeSorted(sortedArray, I, u);
    System.out.println(result);
    }
}

问题是,我似乎无法弄清楚如何构建 withinRangeSorted 方法。

如果我正在搜索大于 I 且小于 u 的值,我主要对方法应该采用哪种参数感到困惑。 我觉得我在这里走在正确的轨道上,但我似乎无法正确地制定递归。

如有任何帮助,我们将不胜感激。

最佳答案

您只需要根据二分查找期间的范围检查来调整数组边界。我很确定参数应该是 l (下)和 u (上)。请注意,我始终将范围视为包含 - 排除。

/**
 * Whether array has at least one element x such that l <= x < u.
 */
boolean withinRangeSorted (int[] array, int l, int u) {
    int start = 0;
    int end = array.length;
    while (start < end) {
        int current = (start + end) / 2;
        if (array[current] >= u) {
            end = current;
        } else if (array[current] < l) {
            start = current + 1;
        } else {
            return true;
        }
    }
    return false;
}

如果您想将其转换为递归实现,请使用 startend作为递归助手的参数。如果您希望范围不是包含 - 排除,请调整 < , <=等和+ 1 , 但要检查差一错误。

关于java - 查看数组是否包含给定范围内的数字,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26704926/

相关文章:

c - 使用 write 递归打印数字 c

java - 如何使用斐波那契方法实现尾递归?

javascript - 如何使用递归将元素插入数组中的所有位置?

java - Maven 和 Junit

java - 如何过滤JSON对象

python - 过滤一组以匹配字符串排列

python - 如何在python中设置多个循环 'for'作为函数的参数来找到将一个句点切成n份的所有可能性?

java - 使用 Proguard 跳过特定警告/注释?

java - 即使在 Windows 中设置类路径,也找不到 SQL Server 驱动程序

c++ - 在 C++ 中将连续范围映射到离散区间