EmptyBinarySearch.java

//http://coolcodebro.blogspot.com/2012/12/find-string-in-array-interspersed-with.html
//Average case: O(log(n)), Worst case: O(n/2) => O(n)

void run() {
	String[] strings = {"at", "", "", "", "ball", "byd", "", "car", "", "", "dad", "", ""};
	String strToFind = "byd";

	System.out.printf("IndexOf \"%s\": %d%n", strToFind, search(strings, strToFind));
}

int search(String[] strings, String find) {
	if(strings == null || strings.length == 0 || find == null || find.length() == 0)
		return -1;

	return searchRec(strings, find, 0, strings.length-1);
}

int searchRec(String[] strings, String find, int low, int high) {
	if(low > high)
		return -1;
	
	int mid = (low + high) / 2;

	//Find the next non-empty string
	if(strings[mid].isEmpty()) {
		int lo = mid;
		int hi = mid;

		while(true) {
			if(lo-- < low || hi++ > high)
				return -1;
			
			if(lo >= low && !strings[lo].isEmpty()) {
				mid = lo;
				break;
			}
			
			if(hi <= high && !strings[hi].isEmpty()) {
				mid = hi;
				break;
			}
		}
	}
	
	//Normal binary search from here
	if(strings[mid].compareTo(find) > 0)
		return searchRec(strings, find, low, mid-1);
	if(strings[mid].compareTo(find) < 0)
		return searchRec(strings, find, mid+1, high);
	
	return mid;
}