Find String

/***

11.5

Given a sorted array of strings which is interspersed with empty strings, write a method to find the location of a given string.

EXAMPLE:

Input: find "ball" in {"at", "", "", "", "ball", "", "", "car", "", "", "dad", "", "",}

Output: 4

***/

#include <iostream>

#include <string>

using namespace std;

int findstr(string *str, string s, int begin, int end) {

    if(end < begin) return -1;

    int mid = (begin + end) / 2;

    if(str[mid] == s) return mid;

    if(str[mid] == "") {

        int left = findstr(str, s, begin, mid-1);

        if(left != -1) return left;

        else return findstr(str, s, mid+1, end);

    } else if(str[mid] > s) {

        return findstr(str, s, begin, mid-1);

    } else return findstr(str, s, mid+1, end);

}

void main() {

    string str[] = {"at", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""};

    int sz = sizeof(str) / sizeof(string);

    int index = findstr(str, "ball", 0, sz-1);

    cout<<index<<endl;

}