#include <iostream>
#include <string>

using namespace std;

int find(string a[], int low, int high, string target){
    int mid = low + (high-low)/2;
    if (low > high)
    	return -1;
    if (a[mid] == target)
    	return mid;
    
    if (a[mid] == ""){
    	int tmp1 = mid -1 ;
    	int tmp2 = mid +1 ;
    	while (a[tmp1] == "" &&  tmp1>0)
    	    tmp1--;
  	    while (a[tmp2] == "" && tmp2 < 12)
  	        tmp2++;
  	    if (target <= a[tmp1]){
  		find(a, low, tmp1, target);
  	    }else{
  		find(a, tmp2, high, target);
  	    }
  	}
  	
  	std::cout << "find did not return a value.\n" ;
 }

int main(){
	string s[13] = {"at", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""};
	cout<< find(s, 0, 12, "car");
}