稀疏数组搜索（面试题10.05）

题目

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

示例

输入: words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ta" 输出：-1

说明: 不存在返回-1。

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

提示

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

算法

二分查找

对于排序数组使用二分查找，这里的问题是会遇到无效的项，对于中点mid是空字符串时：

• 我们将中点位置mid保存在tempMid中
• 将中点mid向右移动直到mid指向不为空且mid小于右端点end
• 当移动mid结束后，判断mid是否等于end+1，如果相等，那么说明[tempMid, end]范围内都是空字符串，我们将右端点收缩到tempMid-1并重新开始二分查找；如果不相等，则按照一般的二分查找判断收缩左端点start还是右端点end

export const findString = (words, s) => {
	let start = 0,
		end = words.length - 1;
	while (start <= end) {
		let mid = ~~((start + end) / 2);
		const tempMid = mid;
		while (words[mid] === "" && mid <= end) mid++;
		if (mid === end + 1) {
			end = tempMid - 1;
			continue;
		}
		if (words[mid] === s) return mid;
		else if (words[mid] < s) start = mid + 1;
		else if (words[mid] > s) end = mid - 1;
	}
	return -1;
};