goden1005

面试题 10.05.稀疏数组搜索

1. 题目描述

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

示例1:

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

示例2:

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

提示:

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

标签 数组 字符串 二分查找

2. 解题

1. 直接遍历

2. 二分查找 查找时，mid可能会落在空字符串上，此时需要向左或向右移动，找到一个非空字符串，从而继续判断应该往左还是往右