题目
原文：
Given a sorted array of strings which is interspersed with empty strings, write a method to find the location of a given string.
Example: find “ball” in [“at”, “”, “”, “”, “ball”, “”, “”, “car”, “”,“”, “dad”, “”, “”] will return 4
Example: find “ballcar” in [“at”, “”, “”, “”, “”, “ball”, “car”, “”, “”, “dad”, “”, “”] will return -1
译文：
给你一个排好序的并且穿插有空字符串的字符串数组，写一个函数找到给定字符串的位置。
例子：在字符串数组 [“at”, “”, “”, “”, “ball”, “”, “”, “car”, “”,“”, “dad”, “”, “”] 中找到”ball”，返回下标4.
例子：在字符串数组 [“at”, “”, “”, “”, “”, “ball”, “car”, “”, “”, “dad”, “”, “”] 中找到”ballcar”，查找失败，返回-1.
解答
字符串数组已经是有序的了，所以，还是可以利用二分查找来找到指定的字符串。 当然了，由于数组中有空字符串，因此还要加些额外的处理，否则无法对比大小。 我们可以这样来处理，如果要对比的那个元素为空字符串，就一直向右移动， 直到字符串不为空或是位置已经超出了high下标。如果位置已经超出high下标， 就在[low, mid-1]这一段查找；如果没有超出high下标，那就和要查找的x进行对比。 相等时返回下标，不等时再根据比较出的大小决定到哪一半去查找。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
using namespace std;
int search(string s[], int low, int high, string x){
if(x == "") return -1;
while(low <= high){
int mid = (low+high)>>1;
int t = mid;
while(s[t] == "" && t <= high) ++t;
if(t > high) high = mid - 1;
else{
if(s[t] == x) return t;
else if(s[t] < x) low = t + 1;
else high = mid - 1; //or t-1
}
}
return -1;
}
int main(){
string s[13] = {
"at", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""
};
cout<<search(s, 0, 12, "ball")<<endl;
return 0;
}
全书题解目录：
Cracking the coding interview–问题与解答
全书的C++代码托管在Github上：
https://github.com/Hawstein/cracking-the-coding-interview
声明：自由转载-非商用-非衍生-保持署名 | 创意共享3.0许可证，转载请注明作者及出处
出处：http://hawstein.com/2013/01/20/9.5/
