难度: Easy
稀疏数组搜索。有个排好序的字符串数组，其中散布着一些空字符串，编写一种方法，找出给定字符串的位置。
示例1:
输入: words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ta" 输出：-1 说明: 不存在返回-1。
示例2:
输入：words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ball" 输出：4
提示:
运行时间: 21 ms
内存: 16.3 MB
class Solution:
def findString(self, words: List[str], s: str) -> int:
left, right = 0, len(words) - 1
while left <= right:
mid = left + (right - left) // 2
temp = mid
while words[mid] == '' and mid < right:
mid += 1
if words[mid] == '':
right = temp - 1
continue
if words[mid] == s:
return mid
elif s < words[mid]:
right = mid - 1
else:
left = mid + 1
return -1
这个题解采用了一个二分查找的变体来处理含有空字符串的排序字符串数组。算法的核心是在常规的二分查找基础上加入了对空字符串的处理。在查找中值mid时，如果发现words[mid]是空字符串，则向右移动mid，直到找到非空字符串或者到达数组的右界。如果整个区间mid到right都是空字符串，那么调整搜索的右界限为mid左边的位置；如果找到了非空字符串，则比较这个字符串和目标字符串s。如果相等，则返回mid的位置；如果目标字符串小，则左移右界；反之，则右移左界。
时间复杂度: O(n)
空间复杂度: O(1)
# 定义一个解决方案类
class Solution:
def findString(self, words: List[str], s: str) -> int:
left, right = 0, len(words) - 1 # 初始化左右指针
while left <= right:
mid = left + (right - left) // 2 # 二分查找中值
temp = mid # 记录原始中间位置
while words[mid] == '' and mid < right: # 向右移动，跳过空字符串
mid += 1
if words[mid] == '':
right = temp - 1 # 如果mid到right全为空，则调整右边界
continue
if words[mid] == s:
return mid # 找到目标字符串，返回索引
elif s < words[mid]:
right = mid - 1 # 目标小于中点字符串，调整右界
else:
left = mid + 1 # 目标大于中点字符串，调整左界
return -1 # 未找到，返回-1
在稀疏数组中进行二分查找时，选择先向右移动mid以跳过空字符串而不是向左移动的原因主要是由于二分查找的初始mid位置是向左偏的（由于整数除法的特性）。因此，向右移动是为了更快地接近中间的非空字符串，尤其是在右半部分可能有更多连续的非空字符串的情况下。这种策略简化了逻辑，因为一旦向右移动找到非空字符串后，可以直接进行比较，而无需再回头处理左侧可能错过的非空字符串。
在二分查找过程中，如果从mid向右移动直到数组末尾都是空字符串，将右界调整到mid左边的位置是安全的。这是因为，如果目标字符串s存在于数组中，它必然位于mid左侧的非空区域。此时缩小搜索范围到左侧，不会错过目标字符串s，因为右侧已经确认全为无效的空字符串，不可能包含目标字符串。
在数组两端存在大量空字符串的情况下，这种基本的二分查找算法可能在效率上受到影响，因为需要额外的步骤来跳过这些空字符串，尤其是在边界情况下。一种可能的优化策略是在实施二分查找之前，先通过扫描来确定非空字符串的实际边界，然后在这个确定的区间内应用二分查找。这样可以减少中间过程中对空字符串的多次检测和跳过，从而提高算法的整体效率。