Find string in sorted array with interspersed empty strings

Question

(from McDowell) Given a sorted array of strings which is interspersed with empty strings, find the location of a given string. eg. "ball" in

{"at", "", "", "", "ball", "", "", "car",
            "", "", "dad", "",""}

would output 4

Any comments on the code below?

Also, correct me if I am wrong please: - space complexity: in place - time complexity: worst case O(n), average case O(log(n))

  public static int findString(String[] array, String target, int low, int high){
    if (high < low) return -1;

    int middle = (low+high)/2;

    if (array[middle].equals(target)) return middle;

    if (array[middle].equals("")){
      int left = middle;
      int right = middle;

      while (array[left].equals("") && left >= low) left--;
      while (array[right].equals("") && right <= high)  right++;

      if (array[left].compareTo(target) >= 0) return findString(array, target, low, left);
      else if (array[right].compareTo(target) <= 0) return findString(array, target, right, high);
      else  return -1;
    }
    else{
      if (array[middle].compareTo(target) >= 0) return findString(array, target, low, middle);
      else if (array[middle].compareTo(target) <= 0) return findString(array, target, middle, high);
      else  return -1;      
    }
  }

Answer 1

Bugs

To demonstrate some corner cases, I will assume we have this convenient wrapper method (which I recommend to add anyway):

public static int findString(String[] array, String target) {
    return findString(array, target, 0, array.length - 1);
}

Given the input {"", "", "a"}, "0", this code will result in ArrayIndexOutOfBoundsException:

  while (array[left].equals("") && left >= low) left--;

Because array[left] will be accessed after left becomes -1. A quick remedy is to flip the operands of &&:

  while (left >= low && array[left].equals("")) left--;

But then, this line will fail too for the same reason:

  if (array[left].compareTo(target) >= 0) return findString(array, target, low, left);

To prevent that, you would need to add the left >= low condition here too, before accessing array[left]:

  if (left >= low && array[left].compareTo(target) >= 0) return findString(array, target, low, left);

Follow the same argument and fix for right too.

But actually this is still not enough. In the above example input, high will reach 0, low stays at 0, and an infinite recursion occurs until a StackOverflowError. so early in the function you need to add a condition on high == 0 too:

// ...

if (array[middle].equals(target)) return middle;
if (high == 0) return -1;

// ...

Unnecessary elements

This condition is unnecessary:

if (high < low) return -1;

The rest of the implementation automatically handles this case.

---

The last part of the function can be simplified:

else{
  if (array[middle].compareTo(target) >= 0) return findString(array, target, low, middle);
  else if (array[middle].compareTo(target) <= 0) return findString(array, target, middle, high);
  else  return -1;      
}

This way is exactly the same, but simpler:

if (array[middle].compareTo(target) >= 0) return findString(array, target, low, middle);
return findString(array, target, middle, high);

Notice also that the >= 0 condition can be just > 0

Unit testing

To verify that your implementation works in the different cases, especially the corner cases, it's good to have some unit tests, for example:

@Test
public void test_0x() {
    assertEquals(-1, findString(new String[]{"", "", "a"}, "0"));
}

@Test
public void test_0() {
    assertEquals(-1, findString(new String[]{"", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""}, "a"));
}

@Test
public void test_z() {
    assertEquals(-1, findString(new String[]{"", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""}, "z"));
}

@Test
public void test_a() {
    assertEquals(-1, findString(new String[]{"at", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""}, "a"));
}

@Test
public void test_ball() {
    assertEquals(4, findString(new String[]{"at", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""}, "ball"));
}

@Test
public void test_at() {
    assertEquals(0, findString(new String[]{"at", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""}, "at"));
}

@Test
public void test_car() {
    assertEquals(7, findString(new String[]{"at", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""}, "car"));
}

@Test
public void test_dad() {
    assertEquals(10, findString(new String[]{"at", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""}, "dad"));
}

@Test
public void test_core() {
    assertEquals(-1, findString(new String[]{"at", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""}, "core"));
}

Coding style

It's recommended to use braces with even single-statement if, for and while statements too. So instead of:

if (array[middle].equals(target)) return middle;
if (high == 0) return -1;

This is better:

if (array[middle].equals(target)) {
    return middle;
}
if (high == 0) {
    return -1;
}

---

It's recommended to declare and initialize variables close to where they are actually used. So instead of:

int left = middle;
int right = middle;

while (left >= low && array[left].equals("")) left--;
while (right <= high && array[right].equals("")) right++;

if (left >= low && array[left].compareTo(target) >= 0) return findString(array, target, low, left);
else if (right <= high && array[right].compareTo(target) <= 0) return findString(array, target, right, high);
return -1;

This is better:

int left = middle;
while (left >= low && array[left].equals("")) left--;
if (left >= low && array[left].compareTo(target) >= 0) return findString(array, target, low, left);

int right = middle;
while (right <= high && array[right].equals("")) right++;
if (right <= high && array[right].compareTo(target) <= 0) return findString(array, target, right, high);
return -1;

And this is equivalent, but more efficient:

int left = middle;
while (left >= low && array[left].equals("")) left--;
if (left < low) return -1;
if (array[left].compareTo(target) >= 0) return findString(array, target, low, left);

int right = middle;
while (right <= high && array[right].equals("")) right++;
if (right > high) return -1;
if (array[right].compareTo(target) <= 0) return findString(array, target, right, high);

---

Instead of .equals(""), it's better to use .isEmpty().