二分查找有序数组

盛夏的果实

昨天百度面试，问了这样一道题：
对于一个有序字符串数组，用二分法查找某一字符串是否存在于该字符串数组中。函数原型为：

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 }