public class PinduoduoOne {

    public static int search(String[] s, String target) {
        int left = 0, right = s.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            // 记录最开始的mid
            int originMid = mid;
            while (mid <= right && s[mid].equals("")) {
                mid++;
            }
            // 如果mid超过了搜索right边界，说明mid～right部分全为空串
            if (mid > right) {
                right = originMid - 1;
                continue;
            }
            // target > [mid]
            if (target.compareTo(s[mid]) > 0) {
                left = mid + 1;
            } else if (target.compareTo(s[mid]) < 0) {
                right = mid - 1;
            } else {
                return mid;
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        System.out.println(search(new String[]{"ac", "", "", "", "", "", "", "", "", "ad", "b", "", "ba"}, "ac"));
        System.out.println(search(new String[]{"", "", "ac", "", "", "", "", "", "", "", "", "ad", "b", "", "ba"}, "ac"));
    }
}