Erratum
The supplied solution isn’t complete and will get into run-time error:
i.e. Add the following lines in the main method in the solution section.
int low = find_low_index(array, 8);
int high = find_high_index(array, 8);
System.out.println("LowIndex of 8 : "+ low);
System.out.println("HighIndex of 8 : "+ high);
Leetcode
I wasn’t able to find corresponding Leetcode example for this problem.
Correction & Alternative solution
class findLowHigh{
static int find_low_index(List<Integer> arr, int key) {
int min = 0;
int max = arr.size() - 1;
while (min <= max) {
int mid = min + (max - min) / 2;
if (arr.get(mid) < key) {
min = mid + 1;
} else {
max = mid - 1;
}
}
// Must check whether index is within the bound
if (min < arr.size() && arr.get(min) == key) return min;
return -1;
}
// Possible alternative solution
static int find_high_index(List<Integer> arr, int key) {
int min = 0;
int max = arr.size() - 1;
while (min <= max) {
int mid = min + (max - min) / 2;
if (arr.get(mid) == key) {
// Instead of checking value of min/max after escaping the while loop,
// We can do it here.
if (arr.get(max) == key) {
return max;
} else {
min = mid;
max = max - 1;
}
} else if (arr.get(mid) < key) {
min = mid + 1;
} else {
max = mid - 1;
}
}
return -1;
}
}