【二分查找】面试题 10.05. 稀疏数组搜索

 1 class Solution {
 2 public:
 3     int findString(vector<string>& words, string s) 
 4     {
 5         int left = 0;
 6         int right = words.size() - 1;
 7 
 8         while (left <= right)
 9         {
10             // 补丁1: 存在重复
11             while (words[left] == "" && left < right) 
12             {
13                 left++;
14             }
15             // 补丁2：存在重复
16             while (words[right] == "" && left < right) 
17             {
18                 right--;
19             }
20 
21             int mid = left + (right - left) / 2;
22             
23             // 补丁3:存在重复
24             while (words[mid] == "" && mid < right) 
25             {
26                 mid++;
27             }
28 
29             // 正常的二分查找
30             if (words[mid] == s)
31             {
32                 return mid;
33             }
34             else if (words[mid] < s)
35             {
36                 left = mid + 1;
37             }
38             else if (words[mid] > s)
39             {
40                 right = mid - 1;
41             }
42         }
43 
44         return -1;
45     }
46 };