题解 | #在有序但是含有空的数组中查找字符串#

//再介绍使用二分查找的方法
//本题字符串数组是递增的，所以很容易想到用二分法
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    string str;
    cin>>str;
    string arr[n];
    for(int i=0;i<n;i++)
        cin>>arr[i];
    int l=0,r=n-1;
    while(l<=r){
        int mid=(l+r)/2;
        if(arr[mid]=="0"){//当前遇到了空字符串
            int temp=r;//记下当前r所在的位置
            r=mid-1;
            while(r>=l&&arr[r]=="0"){
                r--;
            }
            if(r<l){//说明左半区全是空字符串
                l=mid+1;
                r=temp;
            }
            else{//说明遇到了非空字符串
                if(arr[r]>=str){
                    continue;
                }
                else{
                    r=temp;
                    l=mid+1;
                }
            }
        }
        if(arr[mid].compare(str)==0){//相等,找最左位置
            r=mid-1;
        }
        
        
        
        else if(arr[mid].compare(str)<0){//比str小
            l=mid+1;
        }
        
        
        else {
            r=mid-1;
        }
        
        
    }
    if(arr[l].compare(str)==0)
        cout<<l<<endl;
    else cout<<-1<<endl;
    return 0;
}