稀疏数组搜索

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

示例1:

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

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

words的长度在[1, 1000000]之间
通过次数11,142提交次数19,921

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sparse-array-search-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
    public int findString(String[] words, String s) {
        if (words == null || words.length == 0 || s == null) return -1;

        int left = 0, right = words.length - 1, mid = 0;
        while (left <= right) {
            mid = left + (right - left) / 2;
            /* 处理mid元素为空字符, 向右寻找非空字符 */
            while (mid <= right && words[mid].equals("")) {
                mid++;
            }
            /* 在区间[mid,right]找不到非空字符, right=mid-1 */
            if (mid > right) {
                right = left + (right - left) / 2 - 1;
                continue;
            }

            if (s.equals(words[mid])) {
                return mid;
            } else if (s.compareTo(words[mid]) < 0) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }

        }
        return -1;
    }
}

赏

谢谢你请我吃糖果

微信