class Finder {
  public:
    int findString(vector<string> str, int n, string x) {
        // write code here
        int start = 0;
        int end = n - 1;
        while (start <= end) {
            int mid = (start + end) / 2;
            int ori_mid = mid;


            while ( mid >= start && str[mid].empty() ) {
                --mid;
            }
            if (mid < start ) {
                mid = ori_mid;
                while ( mid <= end  && str[mid].empty() ) {
                    ++mid;
                }
            }
            if (str[mid] == x) return mid;
            if (str[mid] > x)
                end = mid - 1;

            if (str[mid] < x)
                start = mid + 1;

        }
        return -1;
    }
};