class Solution {
public:
int findString(vector<string>& words, string s) {
}
};
面试题 10.05. 稀疏数组搜索
稀疏数组搜索。有个排好序的字符串数组，其中散布着一些空字符串，编写一种方法，找出给定字符串的位置。
示例1:
输入: words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ta" 输出：-1 说明: 不存在返回-1。
示例2:
输入：words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ball" 输出：4
提示:
原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 4.7 MB, 提交时间: 2021-06-23 14:37:58
func findString(words []string, s string) int {
l, r := 0, len(words)-1
for l <= r {
mid := (l+r)/2
for mid > l && words[mid] == "" {
mid--
}
if words[mid] == s {
return mid
} else {
if words[mid] > s {
r = mid-1
} else {
l = mid+1
}
}
}
return -1
}