import java.util.Scanner;
public class Main {
public static void main(String args[]) {
int [] A = {1,2,2,2,2,3,3,3,9,11};
int X;
Scanner s = new Scanner(System.in);
X = s.nextInt();
System.out.println(LowerBound(A,X));
System.out.println(UpperBound(A,X));
}
public static int LowerBound(int [] a , int x)
{int low = 0;
int high = a.length - 1;
int ans = -1;
for (int i=0; low<=high ; i++)
{int mid = (low + high)/2;
if(a[mid]<x)
{low = mid + 1;}
else if(a[mid]>x)
{high = mid -1;}
else if (a[mid]==x)
{ans = mid;
break;}}
return ans;}
public static int UpperBound(int []a,int x)
{int low = 0;
int high = a.length - 1;
int ans = -1;
for(int i=0;low<=high;i++)
{int mid = (low + high)/2;
if (a[mid]<x)
{high = mid - 1;}
else if(a[mid]>x)
{low = mid + 1;}
else if (a[mid]==x)
{ans = mid;
break;} }
return ans; }
}
I AM NOT GETTING CORRECT OUTPUT FROM THIS CODE (told in the video lecture)
WHAT IS THE ERROR IN THE ABOVE CODE???
Upper bound and lower bound codes
There is a small modification … even if you find a[mid]=x still you have to keep on searching again for a even lower or higher index . So here is the modified and correct code … Observe the comments .
1 Like
upperBound function is wrong ,line 38 and 40 is out of bounds
I have modified the code
import java.util.Scanner;
class Main {
public static void main(String args[]) {
int[] A = { 1, 2, 3,3,4 };
int X;
Scanner s = new Scanner(System.in);
X = s.nextInt();
System.out.println(LowerBound(A, X));
System.out.println(UpperBound(A, X));
}
public static int LowerBound(int[] a, int x) {
int low = 0;
int high = a.length - 1;
int ans = -1;
for (int i = 0; low <= high; i++) {
int mid = (low + high) / 2;
if (a[mid] < x) {
low = mid + 1;
} else if (a[mid] > x) {
high = mid - 1;
} else if (a[mid] == x) {
ans = mid;
high = mid - 1; // To find the lower bound move the pointer
}
}
return ans;
}
public static int UpperBound(int[] a, int x) {
int low = 0;
int high = a.length - 1;
int ans = -1;
for (int i = 0; low <= high; i++) {
int mid = (low + high) / 2;
if (a[mid] < x) {
low = mid + 1;
} else if (a[mid] > x) {
high = mid - 1;
} else if (a[mid] == x) {
ans = mid;
low = mid + 1; // To find the upper bound move the pointer up
}
}
return ans;
}
}