菜鸟笔记昨天百度面试，问了这样一道题：
对于一个有序字符串数组，用二分法查找某一字符串是否存在于该字符串数组中。函数原型为：
bool BinarySearch(const vector<string>& array, const string& target)
注意这里的有序指的是字典序，如字符串数组 a, ab, ac, bc, cd, d 就是有序字符串数组，而 a, b, ab 及 a, ac, ab 都不是有序字符串数组。
对于这道题，一种很笨的做法是：
1 #include <iostream>
2 #include <vector>
3 #include <string>
4 #include <map>
5 #include <algorithm>
6 using namespace std;
7
8 bool BinarySearch(const vector<string>& array, const string& target);
9 int getUpperBound(const vector<string>& array, const string& target, int index, int low, int high);
10 int getLowerBound(const vector<string>& array, const string& target, int index, int low, int high);
11
12 int main()
13 {
14 vector<string> vec{ "ab", "abc", "abc", "abcd", "bcd", "bcde" };
15 string target{ "abcd" };
16
17 bool ret = BinarySearch(vec, target);
18
19 return 0;
20 }
21
22 bool BinarySearch(const vector<string>& array, const string& target)
23 {
24 if (array.size() == 0 && target.length() == 0)
25 return false;
26 else if (array.size() == 0 && target.length() != 0)
27 return false;
28 else if (array.size() != 0 && target.length() == 0)
29 {
30 if (array[0].empty())
31 return true;
32 else
33 return false;
34 }
35 else
36 {
37 int len = target.length();
38 int low = 0, high = array.size() - 1;
39 for (int i = 0; i < len; i++)
40 {
41 int tmpLow = getLowerBound(array, target, i, low, high);
42 int tmpHigh = getUpperBound(array, target, i, low, high);
43 low = tmpLow;
44 high = tmpHigh;
45 if (low == high)
46 break;
47 }
48
49 if (array[low] == target)
50 return true;
51 }
52
53 return false;
54 }
55
56 int getUpperBound(const vector<string>& array, const string& target, int index, int low, int high)
57 {
58 if (low >= high)
59 return low;
60
61 while (low < high)
62 {
63 int mid = (low + high) / 2 + 1;
64 if ((index < array[mid].size() && array[mid][index] == target[index]) || index > array[mid].size())
65 low = mid;
66 else
67 high = mid - 1;
68 }
69
70 return high;
71 }
72
73
74 int getLowerBound(const vector<string>& array, const string& target, int index, int low, int high)
75 {
76 if (low >= high)
77 return low;
78
79 while (low < high)
80 {
81 int mid = (low + high) / 2;
82 if (index < array[mid].size() && array[mid][index] == target[index])
83 high = mid;
84 else if (index > array[mid].size())
85 low = mid + 1;
86 else
87 low = mid + 1;
88 }
89
90 return low;
91 }
View Code
而另一种方法则要简洁得多：
1 #include <iostream>
2 #include <vector>
3 #include <string>
4 using namespace std;
5
6 bool BinarySearch(const vector<string>& array, const string& target);
7
8 int main()
9 {
10 vector<string> vec{ "ab", "abc", "abcd", "bcd", "bcde" };
11 string target{ "abcd" };
12
13 bool ret = BinarySearch(vec, target);
14
15 return 0;
16 }
17
18 bool BinarySearch(const vector<string>& array, const string& target)
19 {
20 if (array.size() == 0 && target.length() == 0)
21 return false;
22 else if (array.size() == 0 && target.length() != 0)
23 return false;
24 else if (array.size() != 0 && target.length() == 0) // array也是可能存在空字符串的，但该空字符串肯定存在于它的第一个元素
25 {
26 if (array[0].empty())
27 return true;
28 else
29 return false;
30 }
31 else
32 {
33 int low = 0, high = array.size() - 1;
34 while (low <= high)
35 {
36 int mid = low + (high - low) / 2;
37 if (target.compare(array[mid]) == 0)
38 return true;
39 else if (target.compare(array[mid]) > 0)
40 low = mid + 1;
41 else
42 high = mid - 1;
43 }
44 }
45
46 return false;
47 }