二分查找 && 稀疏数组搜索 ｜刷题打卡

• 掘金团队号上线，助你 Offer 临门！ 点击 查看详情

一、题目描述

面试题 10.05. 稀疏数组搜索

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

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

示例2:
 输入：words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ball"
 输出：4
提示:

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

二、思路分析

从题目描述中给出了一个特定的条件排好序的字符串数组, 当我们看到排序好的数组题目时，我们优先考虑 二分查找 来解决。这道题也算是一道典型的 二分查找算法题。通过完成这道题，我希望读者朋友能掌握 二分查找 算法的基础步骤，文末附加 二分查找 的通用步骤模版。

我们分析一下问题：一个数组中有一些 排好序 的字符串，而且字符串中间会夹杂着一些空字符串。

我们可以设想一下，如果不考虑参杂的空字符串，让我们去查询某个具体的字符串的下标，是不是入门级别的一道二分查找算法题。那么假设如果没有参杂空字符串，我们应该怎么去解决这个道题呢？

我将采用 TypeScript来解决这道题，ts 对比两个字符串的大小（ASCII码）可以直接通过 < > =去做比较。

朋友们可以通过阅读注释来理解整个 二分查找 思路，相对来讲还是比较清晰的。

不知道有没有朋友会有这样的想法：不就是在数组里面查找某个字符串的下标嘛，我直接遍历数组一个个的去对比不久得了，两行代码就搞定了，简单还好理解。

但是我们想一下，直接遍历的情况下，我们需要对比每一个字符串，最坏的情况如果恰好目标字符串在数组的最后一位或者数组中根本没有目标字符串的时候，时间复杂度可是 O(N) 。 但是对于二分查找法，最坏的情况我们也只需要 logN次对比就能达到目的，这可是指数级别的差距。就比如数组中要是有1亿个字符串时，通过遍历对比，需要执行1亿次；而二分查找法只需要

通过上面的分析我们已经知道了基础版 二分查找法 是怎么操作的了，那么回到最开始的问题，给到我们的字符串并不是单纯的排好序等着我们操作的数组，而是排序字符串数组中随机参杂了空字符串''。这些随机空字符串影响了数组字符串的下标，那么我们还能通过二分查找法来解决这道问题吗？

答案是可以的。

我们还是按照二分查找法通解方法作为主体，然后只要过滤掉特定的情况，比如 middle 字符串是空字符串时做一下特殊处理。

				// 过滤范围中心字符串是空字符串的情况，
        // 因为是空字符串的话，我们不好做对比，就不能确定目标字符串到底是在中间偏左还是偏右
         if (words[i] !== s && words[middle] === '') {
            // 我们把范围稍微缩小一下，不管是改变起始位置还是结束位置，肯定会影响中间middle下标
            // 这里选择改变起始位置，当前你也可以 j--
            i++;
            // 记得要结束本轮循环，因为后面的比较没有任何意义
            continue;
        } else if (words[i] === s){
            // ⚠️!! 这个地方一定要注意，当我们缩小范围而且没有进行二分对比的话
            // 很有可能就把我们的目标字符串漏了，所以这里我们要做一下对比
            return i;
        }

三、AC 代码

四、总结

对于排序数组，我们肯定是要优先考虑 二分查找法 来解决问题的，时间复杂度相对于遍历而言是指数级别的区别。

二分查找法 代码都相似，我们可以总结出代码模板，面试时遇到这类题就直接一把梭。

function findString(words: string[], s: string): number {
    // 首先定义查找的范围，初始化成数组的最大范围，即起始坐标与结尾坐标
    let i = 0;
    let j = words.length - 1;
    // 不断的缩小查找范围，直到搜索范围减小至 0
    while (i <= j) {
        // 取当前查询范围的中间值作为基准用于下方的判断
        let middle = Math.floor((i + j) / 2);
        // 二分查找通用步骤
        if (s > words[middle]) {
            // 如果目标字符串大于最中间的字符串，说明如果目标字符串存在的话，它肯定在中间位置的右边，
            // 那我们是不是就可以把搜索范围的起始位置变为中间位置
            i = middle + 1;
        } else if (s < words[middle]) {
            // 如果目标字符串小于最中间的字符串，说明如果目标字符串存在的话，它肯定在中间位置的左边，
            // 那我们是不是就可以把搜索范围的结束位置变为中间位置
            j = middle - 1;
        } else {
            // 恭喜，找到目标字符串了
            return middle;
        }
    }
    // 如果程序走到这里了，说明数组中并没有目标字符串，那么就返回 -1
    return -1;
};