Need some java help with a question for my program. I worked with a partner so I
ID: 3591519 • Letter: N
Question
Need some java help with a question for my program. I worked with a partner so I'm not 100% sure on my answer I'm mainly here to double check.
1. Describe how your firstIndexOf() method in BinarySearchDeluxe.jav finds the first index of a key that equals the search key.
Here is the part of my program that relates to the question.
public static <Key> int firstIndexOf(Key[] a, Key key, Comparator<Key> comparator) {
if (a == null || key == null || comparator == null){
throw new NullPointerException("Cannot find first key index");
}
//if not found
if (a.length == 0){
return -1;
}
//Binary Search Algorithm
int left = 0;
int right = a.length - 1;
while (left + 1 < right){
int mid = left + (right - left) / 2;
if (comparator.compare(key, a[mid]) <= 0){
right = mid;
}
else{
left = mid;
}
}
if (comparator.compare(key, a[left]) == 0){
return left;
}
if (comparator.compare(key, a[right]) == 0) {
return right;
}
return -1;
}
Explanation / Answer
1. What if we get [3,4,6,6,6,6] we need to return INDEX first 6 i.e 2
2. what if we have [3,3,3,3,3,3] we need to return index of first 3 i.e 0
Keeping above test cases in Mind
public static <Key> int firstIndexOf(Key[] a, Key key, Comparator<Key> comparator) {
if (a == null || key == null || comparator == null){
throw new NullPointerException("Cannot find first key index");
}
//if not found
if (a.length == 0){
return -1;
}
//Binary Search Algorithm
int left = 0;
int right = a.length - 1;
while (left <= right){
int mid = left + (right - left) / 2;
if( ( mid == 0 || comparator.compare(key, a[mid-1]) > 0 ) && comparator.compare(key, a[mid]) == 0)
return mid;
else if (comparator.compare(key, a[mid]) > 0){
left = mid + 1 ;
}
else{
right = mid - 1;
}
}
return -1;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.