# Accepted Java Solution with Explanation

• It's important to locate sub-interval within A that falls between [lower, upper], and we should do this in O(logn) instead of O(n) (maybe LC didn't check this?)
This is my accepted Java solution:

``````/**
* first, handle special cases where A is empty or
* A is complete out of range [lower, upper].
* Then, use binary search to locate the interval on A that is
* within range [lower, upper].
* Last:
* 1. check lower vs first element of interval.
* 2. iterate through each element and compare against prev.
* 3. check last element of interval vs upper.
*/
public List<String> findMissingRanges(int[] A, int lower, int upper) {
List<String> results = new ArrayList<String>();

// index of first element >= lower
int head = firstLargerEqual(A, 0, A.length-1, lower);
// index of last element <= upper
int tail = lastLessEqual(A, 0, A.length-1, upper);
if (head < 0 && tail < 0)
else {
for (int i = head+1; i <= tail; i++)
}

return results;
}

// return index of first element >= target; if none, return -1.
private int firstLargerEqual(int[] array, int start, int end, int target) {
if (start > end)
return -1;
int mid = start + (end - start)/2;
if (array[mid] >= target) {
if (mid - 1 < start || array[mid-1] < target)
return mid;
else
return firstLargerEqual(array, start, mid-1, target);
} else {
return firstLargerEqual(array, mid+1, end, target);
}
}

// return index of last element <= target; if none, return -1.
private int lastLessEqual(int[] array, int start, int end, int target) {
if (start > end)
return -1;
int mid = start + (end-start)/2;
if (array[mid] <= target) {
if (mid + 1 > end || array[mid+1] > target)
return mid;
else
return lastLessEqual(array, mid+1, end, target);
} else {
return lastLessEqual(array, start, mid-1, target);
}
}

// add a range to list
private void add(int num1, int num2, List<String> results) {
if (num1 <= num2) {
if (num1 == num2)