LeetCodeInHardWay/src/Problem_10.04_findString.cc at master · yinghaoyu/LeetCodeInHardWay · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <string>
#include <vector>

using namespace std;

class Solution
{
 public:
  int findString(vector<string>& words, string s)
  {
    int left = 0, right = words.size() - 1;

    while (left <= right)
    {
      int mid = (left + right) / 2;

      if (words[mid] == "")
      {
        // 退化成线性
        // 为了效率，只需找到距离最近的非空单词位置
        int l = mid - 1, r = mid + 1;
        while (true)
        {
          if (l < left && r > right)
          {
            return -1;
          }
          if (r <= right && words[r] != "")
          {
            mid = r;
            break;
          }
          if (l >= left && words[l] != "")
          {
            mid = l;
            break;
          }
          l--;
          r++;
        }
      }

      if (words[mid] == s)
      {
        return mid;
      }
      else if (words[mid] < s)
      {
        left = mid + 1;
      }
      else
      {
        right = mid - 1;
      }
    }

    return -1;
  }
};