Searching in a sorted array of strings with empty strings

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

My initial thoughts:
The worst we can do is O(n) where we just do a linear search. I tried to do better in the sense that we do a binary search, however if we encounter “”, we have to exam both sides. In this way, worst case we still do a O(n) search but in average, it’s better off.

My initial codes:

	public static int findLocation(String[] array, int i, int j, String str) {
		int mid;
		while (i <= j) {
			mid = (i + j) / 2;
			if (array[mid].equals("")) {
				int leftIndex = findLocation(array, i, mid - 1, str);
				if (leftIndex == -1)
					return findLocation(array, mid + 1, j, str);
				else
					return leftIndex;
			} else {
				if (str.compareTo(array[mid]) == 0)
					return mid;
				if (str.compareTo(array[mid]) < 0)
					j = mid - 1;
				if (str.compareTo(array[mid]) > 0)
					i = mid + 1;
			}
		}
		return -1;
	}

Solution:

	public static int search(String[] strings, String str, int first, int last) {
		while (first <= last) {
			// Ensure there is something at the end
			while (first <= last && strings[last] == "") {
				--last;
			}
			if (last < first) {
				return -1; // this block was empty, so fail
			}
			int mid = (last + first) >> 1;
			while (strings[mid] == "") {
				++mid; // will always find one
			}
			int r = strings[mid].compareTo(str);
			if (r == 0)
				return mid;
			if (r < 0) {
				first = mid + 1;
			} else {
				last = mid - 1;
			}
		}
		return -1;
	}

	public static int search(String[] strings, String str) {
		if (strings == null || str == null)
			return -1;
		if (str == "") {
			for (int i = 0; i < strings.length; i++) {
				if (strings[i] == "")
					return i;
			}
			return -1;
		}
		return search(strings, str, 0, strings.length - 1);
	}

Comments:

  1. Worst case time complexity is still O(n) since in the worst case, you need to remove all the “”s.
  2. Covers the cases where the target we are looking for is indeed, empty string. Also some error conditions have been handled.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: