1. 题目
稀疏数组搜索。有个排好序的字符串数组，其中散布着一些空字符串，编写一种方法，找出给定字符串的位置。
示例1:输入: words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ta"输出：-1说明: 不存在返回-1。示例2:输入：words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ball"输出：4提示:words的长度在[1, 1000000]之间
来源：力扣（LeetCode）
链接：https://leetcode-/problems/sparse-array-search-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
将非空字符串和其序号，存起来二分查找字符串，返回其序号class Solution {public:int findString(vector<string>& words, string s) {vector<pair<string,int>> w_id;for(int i = 0; i < words.size(); ++i)if(words[i] != "")w_id.push_back({words[i],i});int l = 0, r = w_id.size()-1, mid;while(l <= r){mid = l+((r-l)>>1);if(s < w_id[mid].first)r = mid-1;else if(s > w_id[mid].first)l = mid+1;elsereturn w_id[mid].second;}return -1;}};
上面画蛇添足了，直接遍历过一遍了，还二分查找。。直接二分查找如下：需要对空字符串进行处理跳过，mid 也是挪至非空处
class Solution {public:int findString(vector<string>& words, string s) {int l = 0, r = words.size()-1, mid;while(l <= r){while(l <= r && words[l]=="")l++;while(l <= r && words[r]=="")r--;mid = l+((r-l)>>1);while(l <= mid && words[mid]=="")mid--;// while(r >= mid && words[mid]=="") //这样写也行// mid++;if(s < words[mid])r = mid-1;else if(s > words[mid])l = mid+1;elsereturn mid;}return -1;}};
