所以,我遇到了一个问题,要实现一个程序,如果排序后的整数数组包含大于 I
但小于 的数字,则该程序返回
,否则为 true
ufalse
。
我已经确定快速排序算法是对数组进行排序的好方法,因为我不知道用户将如何输入它 - 然后,我将排序后的数组提供给二进制搜索并找出是否该数组包含指定范围内的整数。 问题是,我似乎无法对此进行推理,因为它不是我想在这里找到的一个值,而是一个范围。 另外,如果可能的话,我想递归地实现它。
这是我目前所拥有的:
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;
}
如果您想将其转换为递归实现,请使用 start
和 end
作为递归助手的参数。如果您希望范围不是包含 - 排除,请调整 <
, <=
等和+ 1
, 但要检查差一错误。
关于java - 查看数组是否包含给定范围内的数字,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26704926/