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

Example: find “ball” in [“at”, “”, “”, “”, “ball”, “”, “”, “car”, “”, “”, “dad”, “”, “”] will return 4
Example: find “ballcar” in [“at”, “”, “”, “”, “”, “ball”, “car”, “”, “”, “dad”, “”, “”] will return -1
                                                                                                                       
Use ordinary binary search, but when you hit an empty string, advance to the next nonempty string; if there is no next non-empty string, search the left half.

1      public int search(String[] strings, String str, int first, int last) {
2              while (first <= last) {
3                       // Ensure there is something at the end
4                       while (first <= last && strings[last] == “”) {
5                               --last;
6                       }
7                       if (last < first) {
8                               return -1; // this block was empty, so fail
9                       }
10                      int mid = (last + first) >> 1;
11                      while (strings[mid] == “”) {
12                              ++mid; // will always find one
13                      }
14                      int r = strings[mid].compareTo(str);
15                      if (r == 0) return mid;
16                      if (r < 0) {
17                              first = mid + 1;
18                      } else {
19                              last = mid - 1;
20                      }
21             }
22             return -1;
23     }
24        
25     public int search(String[] strings, String str) {
26             if (strings == null || str == null) return -1;
27             if (str == “”) {
28                      for (int i = 0; i < strings.length; i++) {
29                              if (strings[i] == “”) return i;
30                      }
31                      return -1;
32             }
33             return search(strings, str, 0, strings.length - 1);
34     }