그래서, 나는 반환하는 프로그램을 구현하는 문제가 주어 졌어 true정렬 된 정수의 배열보다 숫자 이상을 포함하는 경우 I미만을 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;
}
당신은 재귀 구현, 사용이 점을 변환하려는 경우 start와 end재귀 도우미에 인수로. 범위를 포괄적으로 제외하지 않으려면 <, <=등 및을 조정 + 1하되 off-by-one-errors를 확인하십시오.
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다