[CareerCup] 11.5 Search Array with Empty Strings 搜索含有空字符串的数组 - Grandyang - 博客园
11.5 Given a sorted array of strings which is interspersed with empty strings, write a method to find the location of a given string.
EXAMPLE
Input: find "ball" in {"at", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""}
Output: 4
这道题给了我们一个有序的字符串数组，但是在中间加入了很多空字符串，让我们来查找一个给定字符串。如果没有这些空字符串，那么我们用二分查找法很容易搜索，但是这些空字符串就有很大的干扰作用。那么我们要在原有的二分查找法上做修改，类似的修改二分查找法的里有Search in Rotated Sorted Array 在旋转有序数组中搜索和Search in Rotated Sorted Array II 在旋转有序数组中搜索之二。这道题我们的思路是，查找中间的字符串，如果是空字符串，那么我们用二分查找法来找周围最近的非空字符串，然后把mid移到飞空字符串的位置，继续二分查找。相当于二分查找中又嵌套了一个二分查找
Use ordinary binary search, but when you hit an empty string, advance to the next nonempty
https://adaguo.wordpress.com/2013/08/19/find-string/
Read full article from [CareerCup] 11.5 Search Array with Empty Strings 搜索含有空字符串的数组 - Grandyang - 博客园
11.5 Given a sorted array of strings which is interspersed with empty strings, write a method to find the location of a given string.
EXAMPLE
Input: find "ball" in {"at", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""}
Output: 4
这道题给了我们一个有序的字符串数组，但是在中间加入了很多空字符串，让我们来查找一个给定字符串。如果没有这些空字符串，那么我们用二分查找法很容易搜索，但是这些空字符串就有很大的干扰作用。那么我们要在原有的二分查找法上做修改，类似的修改二分查找法的里有Search in Rotated Sorted Array 在旋转有序数组中搜索和Search in Rotated Sorted Array II 在旋转有序数组中搜索之二。这道题我们的思路是，查找中间的字符串，如果是空字符串，那么我们用二分查找法来找周围最近的非空字符串，然后把mid移到飞空字符串的位置，继续二分查找。相当于二分查找中又嵌套了一个二分查找
Use ordinary binary search, but when you hit an empty string, advance to the next nonempty
string; if there is no next non-empty string, search the left half.
Also: http://xiaochongzhang.me/blog/?p=553int search(vector<string> strings, string str) { int first = 0, last = strings.size() - 1; while (first <= last) { int mid = first + (last - first) / 2; if (strings[mid].empty()) { int left = mid - 1, right = mid + 1; while (true) { if (left < first && right > last) return -1; else if (right <= last && !strings[right].empty()) { mid = right; break; } else if (left >= first && !strings[left].empty()) { mid = left; break; } ++right; --left; } } int res = strings[mid].compare(str); if (res == 0) return mid; else if (res < 0) first = mid + 1; else last = mid - 1; } return -1; }http://xiaochongzhang.me/blog/?p=553
int findStrHelper(int begin, int end, vector<string> strings, string target_str)
{
while(begin <= end)
{
while(begin <= end&&strings[end]=="")
--end;
if(begin > end)
return -1;
int mid = begin+(end-begin)/2;
while(strings[mid] == "")
++mid;
if(strings[mid] == target_str)
return mid;
if(strings[mid] < target_str)
begin = mid+1;
else if(strings[mid] > target_str)
end = mid-1;
}
return -1;
}
//--------------------<11.5 find array with interspersed with empty strings>---------------------
int findStr(vector<string> strings, string target_str)
{
if(strings.size() == 0||target_str.size() == 0)
return -1;
if(target_str == "")
{
for(int i = 0; i < strings.size(); ++i)
{
if(strings[i] == "")
return i;
}
return -1;
}
return findStrHelper(0,strings.size()-1, strings, target_str);
}
http://adatechlife.blogspot.com/2013/08/find-string.htmlhttps://adaguo.wordpress.com/2013/08/19/find-string/
int findstr(string *str, string s, int begin, int end) {
if(end < begin) return -1;
int mid = (begin + end) / 2;
if(str[mid] == s) return mid;
if(str[mid] == "") {
int left = findstr(str, s, begin, mid-1);
if(left != -1) return left;
else return findstr(str, s, mid+1, end);
} else if(str[mid] > s) {
return findstr(str, s, begin, mid-1);
} else return findstr(str, s, mid+1, end);
}
https://github.com/1094401996/CareerCup/blob/master/Chapter11/src/elevendot5/FindString.javaRead full article from [CareerCup] 11.5 Search Array with Empty Strings 搜索含有空字符串的数组 - Grandyang - 博客园
