程序员面试金典-面试题 10.05. 稀疏数组搜索

class Solution {
    public int findString(String[] words, String s) {
        return binarySearch(words, s, 0, words.length-1);
    }
    private int binarySearch(String[] words, String s, int l, int r){
        if(l > r){
            return -1;
        }
        if(l == r){
            if(words[l].equals(s))
                return l;
            return -1;
        }
        int mid = l + (r - l) / 2;
        if(!words[mid].equals("")){
            if(s.compareTo(words[mid]) < 0){
                return binarySearch(words, s, l, mid);
            }else if(s.compareTo(words[mid]) > 0){
                return binarySearch(words, s, mid+1, r);
            }else{
                return mid;
            }
        }else{
            int left = mid-1;
            while(left >= l){
                if(words[left].equals("")){
                    left--;
                }else{
                    if(words[left].compareTo(s) < 0)
                        return binarySearch(words, s, mid+1, r);
                    else if(words[left].compareTo(s) > 0)
                        return binarySearch(words, s, l, left);
                    else
                        return left;
                }
            }
            return binarySearch(words, s, mid+1, r);
        }
    }
}