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

示例1:

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

示例2:

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

示例代码1：

class Solution(object):
    def findString(self, words, s):
        """
        :type words: List[str]
        :type s: str
        :rtype: int
        """
        location = 0
        for i in words:
            if i == s:
                return location
            location += 1
        return -1

示例代码2：

class Solution(object):
    def findString(self, words, s):
        """
        :type words: List[str]
        :type s: str
        :rtype: int
        """
        try:
            res = words.index(s)
        except:
            res = -1
        return res

思路解析：

如果直接return words.index(s)， s不存在时会出错
所以try...except，捕获到错误时，返回-1

示例代码3（二分查找）：

class Solution(object):
    def findString(self, words, s):
        """
        :type words: List[str]
        :type s: str
        :rtype: int
        """
        a, b = 0, len(words) - 1  # 左右指针
        mid = (a+b) // 2  # 初始化
        while a <= mid <= b:
            if words[mid]:  # 若words[mid]不为空字符串
                if words[mid] > s:  # 若words[mid]字符串比目标 s 大，则目标 s 一定在左半部分
                    b = mid - 1  # 则右指针减一
                    while a < b and words[b] == '':  # 如果发现指针指向的字符串是空，就继续减一 直到找到非空字符串
                        b -= 1  # 注意条件中需要限制 右指针在左指针的右边
                elif words[mid] < s:
                    a = mid + 1
                    while a < b and words[a] == '':
                        a += 1
                else:
                    return mid
                mid = (a+b) // 2
            # 若words[mid]为空字符串，mid自增1。
            else:
                mid += 1
        return -1