ac(尽可能多的利用二分法)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        String nStr = reader.readLine();
        int n = Integer.valueOf(nStr);
        String str = reader.readLine();
        String[] arr = new String[n];
        for(int i=0;i<n;i++){
            String s = reader.readLine();
            if(s.equals("0")){
                arr[i] = null;
            }else {
                arr[i] = s;
            }
        }
        int firstPos = bsearch(n, arr, str);
        System.out.println(firstPos);
    }

    static int bsearch(int n, String[] arr, String str){
        int left = 0;
        int right = n - 1;
        int ans = -1;
        while (left <= right){
            int mid = (right - left) / 2 + left;
            if(arr[mid] != null){
               if(arr[mid].equals(str)){
                   ans = mid;
                   // 先存一个结果，然后左部分继续二分法
                   right = mid - 1;
               }else if(arr[mid].compareTo(str) > 0){
                   right = mid - 1;
               }else {
                   left = mid + 1;
               }
            }else{
                // 往左找到第一个不是null的字符串(顺序遍历)
                int tmpLeft = mid;
                while (tmpLeft >= 0 && arr[tmpLeft] == null){
                    tmpLeft--;
                }
                if(tmpLeft == -1){ // 左边全是null
                    left = mid + 1;
                }else {
                    if(arr[tmpLeft].equals(str)){
                        ans = tmpLeft;
                        // 先存一个结果，然后左部分继续二分法
                        right = tmpLeft - 1;
                    }else if(arr[tmpLeft].compareTo(str) > 0){
                        right = tmpLeft - 1;
                    }else {
                        left = mid + 1;
                    }
                }
            }
        }
        return ans;
    }

}
/*
8
a
0
a
0
a
ab
ac
0
b

1

4
grep
awk
grep
0
sed

1
 */