gold-10-5

稀疏数组搜索。有个排好序的字符串数组，其中散布着一些空字符串，编写一种方法，找出给定字符串的位置。

示例1:

输入: words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ta"
输出：-1
说明: 不存在返回-1。

示例2:

输入：words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ball"
输出：4

提示:

1. words的长度在[1, 1000000]之间

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    public int findString(String[] words, String s) {
        if (s == null || s.length() == 0) {
            return -1;
        }
        List<Integer> indexList = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            if (words[i] == null || words[i].length() == 0) {
                continue;
            }
            indexList.add(i);
        }

        int start = 0;
        int end = indexList.size() - 1;

        while (start <= end) {
            if (start == end) {
                if (s.equals(words[indexList.get(start)])) {
                    return indexList.get(start);
                } else {
                    break;
                }
            }

            if (start + 1 == end) {
                if (s.equals(words[indexList.get(start)])) {
                    return indexList.get(start);
                } else if (s.equals(words[indexList.get(end)])) {
                    return indexList.get(end);
                } else {
                    break;
                }
            }

            int mid = start + (end - start) / 2;
            String midStr = words[indexList.get(mid)];
            if (midStr.equals(s)) {
                return indexList.get(mid);
            } else if (midStr.compareTo(s) > 0) {
                end = mid;
            } else {
                start = mid;
            }
        }

        return -1;
    }
}
//leetcode submit region end(Prohibit modification and deletion)