Homework Sourselowerbound should return the index of the first lowest index
lower_bound() should return the index of the first (lowest indexed) element of a that is greater than or equal to key, and upper_bound() returns the index of the first (lowest indexed) element of a that is greater than key. You may assume the array is sorted – take that as a hint that something like a binary search is needed. If every element of a is less than the key, both upper_bound and lower_bound return the length of a. If upper_bound returns the length of a.
This is what I currently have. I know I\'m close but I keep getting erros and I am unsure how to fix the code I currently have.
public class Bounds {
public static int lower_bound(int[] a, int key) {
// Your code here.
int len = a.length;
int low = 0;
int high = len-1;
int mid = (low + high)/2;
int compare;
while (true) {
int compare == a[mid].compareTo(key);
if (compare == 0 || compare > 0) {
high = mid-1;
if (high < low)
return mid;
} else {
low = mid+1;
if (high < low)
return mid<len-1?mid+1:-1;
}
mid = (low + high)/2;
}
}
public static int upper_bound(int[] a, int key) {
// Your code here.
int len = a.length;
int lo = 0;
int hi = len-1;
int mid = (lo + hi)/2;
int compare;
while (true) {
int compare == a[mid].compareTo(key);
if (compare == 0 || compare < 0) {
lo = mid+1;
if (hi < lo)
return mid<len-1?mid+1:-1;
} else {
hi = mid-1;
if (hi < lo)
return mid;
}
mid = (lo + hi)/2;
}
}
public static void main(String[] args) {
// The int read from stdin is the size of the array.
int n = StdIn.readInt();
int[] a = new int[n];
// The next n ints are the array itself.
for (int i = 0; i < n; i++)
a[i] = StdIn.readInt();
// Read keys until we have no more input. For each
// key, call lower_bound() and upper_bound() and
// show the results.
while (!StdIn.isEmpty()) {
int key = StdIn.readInt();
int lb = lower_bound(a, key);
int ub = upper_bound(a, key);
StdOut.printf(\"%3d %3d\ \", lb, ub);
}
}
}
Solution
Please follow the code and comments for description :
CODE :
import java.util.Scanner; // required imports for the code to run
public class Bounds { // main class that has the implementations
public static int lower_bound(int[] a, int key) { // method that returns the indexes of the key that is lower than or equal to the key
// Your code here.
int len = a.length; // local varaibles initialaisations
int low = 0;
int high = len - 1;
int mid = (low + high) / 2;
int compare;
Integer value; // Integer value to makes the method compareTo to be compatible to check the key and the data in the array
while (true) { // iterating over the loop till the data in the array is found satisfied
value = a[mid]; // saving the value at the mid of the index
compare = value.compareTo(key); // calling the method compareTo to compare for the key and the element in the array
if (compare == 0 || compare > 0) { // checking for the returned result and proceeding further
high = mid - 1;
if (high < low) { // returning the value is the index of high is less than the low
return mid;
}
} else if (compare == -1) { // if the key is higher than the indexed value at array
low = mid + 1;
if (high < low) {
return mid < len - 1 ? mid + 1 : a.length; // checking for the mid values and returning the next index if it is less or the length of the array if the index is higher.
}
}
mid = (low + high) / 2; // changing the mid values time to time
}
}
public static int upper_bound(int[] a, int key) { // method that returns the indexes of the key that is greater than the key
// Your code here.
int len = a.length; // local varaibles initialaisations
int lo = 0;
int hi = len - 1;
int mid = (lo + hi) / 2;
int compare;
Integer value; // Integer value to makes the method compareTo to be compatible to check the key and the data in the array
while (true) { // iterating over the loop till the data in the array is found satisfied
value = a[mid]; // saving the value at the mid of the index
compare = value.compareTo(key); // calling the method compareTo to compare for the key and the element in the array
if (compare == 0 || compare < 0) { // checking for the returned result and proceeding further
lo = mid + 1; // incermenting the mid value and saving it in the lower index value
if (hi < lo) { // checking for the mid values and returning the next index if it is less or the length of the array if the index is higher.
return mid < len - 1 ? mid + 1 : a.length;
}
} else {
hi = mid - 1;
if (hi < lo) { // returning the value is the index of high is less than the low
return mid;
}
}
mid = (lo + hi) / 2; // changing the mid values time to time
}
}
public static void main(String[] args) { // main driver program of the code
// The int read from stdin is the size of the array.
Scanner sc = new Scanner(System.in); // scanner class to read the data from the user
System.out.println(\"Please Enter the Size of the array : \"); // prompt to user to enter the sizeof the array
int n = sc.nextInt(); // getting th edata from the user
int[] a = new int[n]; // initialaisation of the array with the size
// The next n ints are the array itself.
System.out.println(\"Please Enter the Elements of the Array in a Sorted Way : \"); // prompt for the user to enter the array elements
for (int i = 0; i < n; i++) { // iterating over the size to save the elements
a[i] = sc.nextInt(); // getting the elements
}
// Read keys until we have no more input. For each
// key, call lower_bound() and upper_bound() and
// show the results.
System.out.println(\"Please Enter the Key (-1 to Exit) : \"); // prompt for the user to enter the key values, here -1 indicates the input has been finished, this can be changed based on the user requirement to any other digit
while (sc.hasNext()) { // iterating over the user input
int key = sc.nextInt();
if (key != -1) { // checking for the condition to continue or to stop the loop
int lb = lower_bound(a, key); // calling the method lower_bound to get the first index of the lower bound
int ub = upper_bound(a, key); // calling the method upper_bound to get the first index of the upper bound
System.out.printf(\"The Lower Bound Index is : %3d \ The Upper Bound Index is : %3d\ \", lb, ub); // printing the results
} else {
System.exit(0); // if not satisfied exits the code.
}
}
}
}
OUTPUT :
Please Enter the Size of the array :
5
Please Enter the Elements of the Array in a Sorted Way :
1
2
3
4
5
Please Enter the Key (-1 to Exit) :
2
The Lower Bound Index is : 1
The Upper Bound Index is : 2
3
The Lower Bound Index is : 2
The Upper Bound Index is : 3
5
The Lower Bound Index is : 4
The Upper Bound Index is : 5
6
The Lower Bound Index is : 5
The Upper Bound Index is : 5
-1
Hope this is helpful.
