4
\$\begingroup\$

(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;      
    }
  }
\$\endgroup\$
1
  • 1
    \$\begingroup\$ The average case complexity would be O(log n) if the input were random. Since the only way to wind up with an empty string is by some convention rather than randomization, it's hard to claim 0(log n) average running time. If the sample input is a random sample of the set of inputs, then average running time will be worse than 0(log n). \$\endgroup\$ Feb 17, 2015 at 22:39

1 Answer 1

4
\$\begingroup\$

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().

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Amazing answer thx \$\endgroup\$
    – giulio
    Feb 18, 2015 at 0:38
  • \$\begingroup\$ For the last point, is this really equivalent? If the element is not present on the left side, I still have to look it up on the right side right? \$\endgroup\$
    – giulio
    Feb 18, 2015 at 0:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.