英文:
Finding first and last occurrence of an element using BinarySearch
问题
以下是您的代码的翻译部分：
class FirstAndLastOccurence{
public static int first(int[] arr, int n, int x){
int left = 0;
int right = n-1;
int res = -1;
while(left <= right){
int mid = left + (right-left)/2;
if(x < arr[mid])
right = mid-1;
if(x > arr[mid])
left = mid+1;
else{
res = mid;
right = mid-1;
}
}
return res;
}
public static int last(int[] arr, int n, int x){
int left = 0;
int right = n-1;
int res = -1;
while(left <= right){
int mid = left + (right-left)/2;
if(x < arr[mid])
right = mid-1;
if(x > arr[mid])
left = mid+1;
else{
res = mid;
left = mid+1;
}
}
return res;
}
public static void main(String[] args){
int[] arr = new int[]{2, 4, 10, 10, 10, 10, 56, 71, 90};
System.out.println(first(arr, arr.length, 10));
System.out.println(last(arr, arr.length, 10));
}
}
输出结果：
2
6
第一个输出是正确的，而我的最后一个输出是错误的，因为它应该是 5。我正在尝试遵循的代码在这里（代码不完全相同，我根据我个人的熟悉程度来实现二分搜索）。
英文:
I can find the first occurrence efficiently but I'm having trouble finding the last occurrence. The answer I get for the last occurrence of the element is always the correct index plus one.
Here is my code:
class FirstAndLastOccurence{
public static int first(int[] arr, int n, int x){
int left = 0;
int right = n-1;
int res = -1;
while(left <= right){
int mid = left + (right-left)/2;
if(x < arr[mid])
right = mid-1;
if(x > arr[mid])
left = mid+1;
else{
res = mid;
right = mid-1;
}
}
return res;
}
public static int last(int[] arr, int n, int x){
int left = 0;
int right = n-1;
int res = -1;
while(left <= right){
int mid = left + (right-left)/2;
if(x < arr[mid])
right = mid-1;
if(x > arr[mid])
left = mid+1;
else{
res = mid;
left = mid+1;
}
}
return res;
}
public static void main(String[] args){
int[] arr = new int[]{2, 4, 10, 10, 10, 10, 56, 71, 90};
System.out.println(first(arr, arr.length, 10));
System.out.println(last(arr, arr.length, 10));
}
}
Output:
2
6
The first output is correct while my last output is wrong, as it should have been 5. The code I'm trying to follow is here (the code is not exactly the same, I'm implementing the binary search in a more familiar way to me personally).
答案1
得分: 2
以下是翻译好的代码部分：
public static int last(int[] arr, int n, int x){
int left = 0;
int right = n-1;
int res = -1;
while(left <= right){
int mid = left + (right-left)/2;
if(x < arr[mid])
right = mid-1;
else if(x > arr[mid])
left = mid+1;
else{
res = mid;
left = mid+1;
}
}
return res;
}
英文:
You have added both the if statements and else statement at the last which gets executed only for the second if statement which is incorrect. Please find the below code which is working and giving the correct answer.
public static int last(int[] arr, int n, int x){
int left = 0;
int right = n-1;
int res = -1;
while(left <= right){
int mid = left + (right-left)/2;
if(x < arr[mid])
right = mid-1;
else if(x > arr[mid])
left = mid+1;
else{
res = mid;
left = mid+1;
}
}
return res;
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论