首页 > 代码库 > careercup-排序和查找 11.5
careercup-排序和查找 11.5
11.5 有个排序后的字符串数组，其中散布着一些空字符串，编写一个方法，找出给定字符串的位置。
解法：
如果没有那些空字符串，就可以直接使用二分查找法。比较待查找字符串str和数组的中间元素，然后继续搜索下去。针对数组中散布一些空字符串的情形，我们可以对二分查找法稍作修改，所需的修改就是mid进行比较的地方，如果mid为空字符串，就将mid换到离它最近的非空字符串的位置。
C++实现代码：
#include<iostream>#include<string>#include<vector>using namespace std;int searchR(vector<string> &str,int left,int right,string s){ if(left>right) return -1; int mid=(left+right)/2; if(str[mid].empty()) { int l=mid-1; int r=mid+1; while(1) { if(l<left&&r>right) return -1; if(l>=left&&!str[l].empty()) { mid=l; break; } if(r<=right&&!str[r].empty()) { mid=r; break; } l--; r++; } } if(str[mid]==s) return mid; else if(s<str[mid]) return searchR(str,left,mid-1,s); else return searchR(str,mid+1,right,s);}int search(vector<string> &str,string s){ return searchR(str,0,str.size()-1,s);}int main(){ vector<string> vec= {"","abc","","hfh","jhfh","kdhf","","sss","zzz",""}; cout<<search(vec,string("zzz"))<<endl;}
careercup-排序和查找 11.5
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。