CTCI 11.5

Given a sorted array of strings which is interepersed with empty strings, write a method to find the location of a given string.

CTCI 11.5.java

public static int findLocation(int begin, int end, String input, String[] array){
    if(begin > end) return -1;
    int mid = (begin + end) / 2;
    int leftEnd = mid - 1;
    int rightBegin = mid + 1;
    if(array[mid] == ""){
        while(true){
            if(leftEnd < 0 && rightBegin >= array.length) return -1;
            else if(leftEnd >= 0 && array[leftEnd] != ""){
                mid = leftEnd;
                leftEnd--;
                break;
            }
            else if(rightBegin < array.length && array[rightBegin] != ""){
                mid = rightBegin;
                rightBegin++;
                break;
            }
            leftEnd--;
            rightBegin++;
        }
    }
    if(array[mid].equals(input)) return mid;
    int num = findLocation(begin, leftEnd, input, array);
    if(num == -1) num = findLocation(rightBegin, end, input, array);
    return num;
}