昨天百度面试,问了这样一道题:
对于一个有序字符串数组,用二分法查找某一字符串是否存在于该字符串数组中。函数原型为:
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 }