9.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: find “ball” in [“at”, “”, “”, “”, “ball”, “”, “”, “car”, “”, “”, “dad”, “”, “”] will return 4 Example: find “ballcar” in [“at”, “”, “”, “”, “”, “ball”, “car”, “”, “”, “dad”, “”, “”] will return -1

Normal O(n).

But A better one?

Let‘s binary search.

int search (String[] a, String s)
{
  return search(a, 0, a.length - 1, s);
}

int search (String[] a, int l, int h, String s)
{
  if (l > h)
    return -1;
  
  int m = (l + h) / 2;
  
  // Move to first non empty string
  int nm = m;
  while (a[nm].isEmpty())
  {
   nm ++;
   if (nm  > h) return -1;
  }
  
  if (a[nm] == s)
    return nm;
  else if (a[nm] > s)
    return search(a, l, m - 1, s);
  else 
    return search(a, nm + 1, h, s);
}

CC150 9.5