面试题 10.05. 稀疏数组搜索

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

示例1:

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

示例2:

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

提示:

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

Python 解答：
1.顺序遍历

class Solution:
    def findString(self, words: List[str], s: str) -> int:
        for i in range(len(words)):
            if words[i] == s:
                return i 
        else:
            return -1

2.二分查找

class Solution:
    def findString(self, words: List[str], s: str) -> int: 
        def find(words, s, l, r):
            if l < r:
                mid = (l+r) // 2
                if words[mid] == "":
                    left = find(words, s, l, mid-1)
                    if left != -1:
                        return left
                    else:
                        return find(words, s, mid+1, r)
                elif words[mid] < s:
                    return find(words, s, mid+1, r)
                elif words[mid] > s:
                    return find(words, s, l, mid-1)
                else:
                    return mid
            if 0 <= l < len(words) and words[l] == s:
                return l
            else: return -1
        return find(words, s, 0, len(words)-1)