题目分析

第一眼看上去，直接brute暴力搜索，结果直接通过了，然后好奇心驱使我看了一下其他解法，竟然有更加巧妙的方法。小伙伴们能想得到吗？

二分查找

暴力法在这里我就不叙述了，一个一个比较，相等返回索引，最后返回-1即可。

为什么我一开始想不到二分查找呢？主要是因为一般我们认为要查找的是有序的序列。但是这里存在着一些空串，因此序列并不是有序的。

看了方法之后，我了解到，虽然空串导致序列并不是有序的，但是我们可以忽略空串，当mid所在的字符串为空时，我们可以顺序向下搜索第一个不是空串的位置，用这个位置进行比较。

当仅有words[0]不为空，这时需要遍历所有的情况，因此最坏的情况下算法的**时间复杂度仍是$O(n)$**。

#include<iostream>
#include<vector>

using namespace std;

class Solution {
public:
    int findString(vector<string>& words, string s) {
        int left = 0, right = words.size();
        while (left < right) {
            int mid = (left + right) >> 1;
            if (words[mid] == s) return mid;
            if (words[mid] == "") {
                int cur = mid + 1;
                while (cur < right && words[cur] == "") cur++;
                if (cur == right || words[cur] > s) right = mid;
                else if (words[cur] == s) return cur;
                else left = cur + 1;
            }
            else {
                if (words[mid] > s) right = mid;
                else left = mid + 1;
            }
        }
        return -1;
    }
};

刷题总结

这个题目给我的启发是非常大的，只要数据满足满足除了某些特定元素之外，其他都是有序的，那么我们也可以使用二分进行查找，在大部分数据下时间复杂度都会大大降低。