我想在排序数组中查找给定数字x 的第一次出现。这是我到目前为止的方法:
public static int firstOccur(int[] A, int x, int start, int end){
int first = start;
int last = end;
int result = -1;
while (first <= last){
int mid = (first+last)/2;
if(A[mid] == x){
result = mid;
firstOccur(A, x, first, mid-1);
return result;
}
else if(A[mid] < x){
first = mid+1;
result = firstOccur(A, x, first, last);
}
else if(A[mid] > x){
last = mid-1;
return firstOccur(A, x, first, last);
}
}
return result;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Please enter the value you are looking for: ");
int val = sc.nextInt();
int[] arr = {1,2,2,2,5};
System.out.println("The first occurence of " + val + " is at index " + firstOccur(arr, val, 0, arr.length-1));
}
当我运行代码时，该函数适用于数字1和5以及添加的任何内容。不幸的是，当提交x=2时，它返回索引2，这是不正确的。我是否遗漏了一个小细节？
最佳答案
这里你没有考虑递归函数的返回值
if(A[mid] == x){
result = mid;
firstOccur(A, x, first, mid-1);
return result;
}
更改为
if(A[mid] == x) {
result = mid;
int maybeResultToLeft = firstOccur(A, x, first, mid-1);
if (maybeResultToLeft == -1) {
return result;
}
return maybeResultToLeft;
}
或者一句单行
return maybeResultToLeft == -1? result : maybeResultToLeft;
我们需要选择当前 (x) 元素左侧的元素 (x)(如果存在 - maybeResultToLeft != -1)
关于java - 递归查找排序数组中第一次出现的数字，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/52503113/