✅面试题 10.05. 稀疏数组搜索

[Ray-56]

面试题 10.05. 稀疏数组搜索

题目

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

示例1：

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

示例2：

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

[Ray-56]

注意审题，稀疏数组是已排好序的，找某个的最优方法就是二分查找

/**
 * @param {string[]} words
 * @param {string} s
 * @return {number}
 */
var findString = function(words, s) {
	if (words === null || words.length === 0) return -1;
	
	let left = 0;
	let right = words.length - 1;
	while (left <= right) {
		while (words[left] === '') left++;
		while (words[right] === '') right--;
		let mid = left + Math.floor((right - left) / 2);
		
		while (words[mid] === '' && mid < right) mid++;

		if (words[mid] === s) return mid;

		// 根据第一个不同的字符的ascii值码进行比较
		if (s < words[mid]) {
			right = mid - 1;
		} else {
			left = mid + 1;
		}
	}
	
	return -1;
};