二分查找有序数组-ag真人游戏

　　昨天百度面试，问了这样一道题：

　　对于一个有序字符串数组，用二分法查找某一字符串是否存在于该字符串数组中。函数原型为：

bool binarysearch(const vector& array, const string& target)

　　注意这里的有序指的是字典序，如字符串数组 a, ab, ac, bc, cd, d 就是有序字符串数组，而 a, b, ab 及 a, ac, ab 都不是有序字符串数组。

　   对于这道题，一种很笨的做法是：

 1 #include 
 2 #include 
 3 #include 
 4 #include 

view code

　　而另一种方法则要简洁得多：

 1 #include 
 2 #include 
 3 #include 
 4 using namespace std;
 5 
 6 bool binarysearch(const vector& array, const string& target);
 7 
 8 int main() 
 9 {
10     vector 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& 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 }