Search an ascending String array interspersed with empty Strings

The problem is stated as:

Given a String array arr, where all the strings in it is pre-sorted in ascending order, however, there are indefinite number of empty strings in it as well. For example,

arr={"", "", "", "36b", "ich099tb", "yi", "zrdy46", "", "", "", ""}

We can tackle this problem by using a modified binary search, and I came up with one recursion solution as well as an iterative one. The code is again simple. I first provide the test code, the implementation follows.

Test Code

	Random r = new Random();
	/**
	 * Return a randomly generated String array follows the rule
	 *
	 * @param size
	 * @return
	 */
	private String[] getAscendingStringArrayWithEmpty(int size){
		int emptyStringCount = r.nextInt(size+1);
		int count = size-emptyStringCount;
		String[] result = new String[size];
		HashSet<String> set = new HashSet<String>();
		ArrayList<String> nonEmptyStrings = new ArrayList<String>();
		while(set.size()<=count){
			set.add(StringHelper.randomStringGenerator(r.nextInt(10)));
		}
		nonEmptyStrings.addAll(set);
		Collections.sort(nonEmptyStrings);
		while(count+emptyStringCount>0){
			boolean b = r.nextBoolean();
			if(b && count>0){	//insert a non-empty string
				result[count+emptyStringCount-1] = nonEmptyStrings.get((count--)-1);
			}else{	//insert an empty string
				result[count+(emptyStringCount--)-1] = "";
			}
		}
		return result;
	}
	@Test
	public void testSearchArrayWithEmptyString(){
		for(int j=0; j<100; j++){
			String[] arr = getAscendingStringArrayWithEmpty(1<<15);
			for(int i=0; i<arr.length; i++){
				if(arr[i].trim().length()!=0){
					Assert.assertEquals(i, SortingQuestions.searchArrayWithEmpty(arr, arr[i]));
				}
			}
		}
	}

Implementation: Recursion

	/**
	 * Given a sorted array of strings which is interspersed with empty strings,
	 * write a method to find the location of a given string.
	 */
	public static int searchArrayWithEmptyString(String[] arr, String t){
		if(arr==null || t==null)
			return -1;
		return searchArrayWithEmptyString(arr, t, 0, arr.length-1);
	}
	private static int searchArrayWithEmptyString(String[] arr, String t, int left, int right){
		if(left>right)
			return -1;
		int mid = (left+right)>>1;
		if(arr[mid].equals(t))
			return mid;
		int a=-1, b=-1;
		if(mid>left)
			a = searchArrayWithEmptyString(arr, t, left, mid-1);
		if(mid<right)
			b = searchArrayWithEmptyString(arr, t, mid+1, right);
		/**
		 * if a==-1, means not found on the left;
		 * if b==-1, means not found on the right;
		 */
		if(a!=-1)
			return a;
		else if(b!=-1)
			return b;
		else
			return -1;
	}

Implementation: Iterative

	/**
	 * Iterative approach
	 *
	 * @param arr The given string array must in ascending order excludes whitespace
	 * @param t Given string to search
	 * @return index of the target if found; -1 otherwise
	 * @throws NullPointerException if either array or given string is null
	 * @throws IllegalArgumentException If 1) given string is empty; 2) given array is not in order
	 */
	public static int searchArrayWithEmpty(String[] arr, String t){
		if(arr==null || t==null)
			throw new NullPointerException("Either array or given string is null");
		if(arr.length==0)
			return -1;
		if(t.trim().length()==0)
			throw new IllegalArgumentException("Search terms can not be empty");
		int left = 0;
		int right = arr.length-1;
		while(left<=right){
			int mid = (left+right)>>>1;
			int mid1 = mid;
			if(arr[mid].equals(t))
				return mid;
			/*
			 * find the first non-empty string to the right,
			 * if all the strings on the right are empty, mid will end up with
			 * larger than right(out of bound)
			 */

			while(mid<=right && arr[mid].trim().length()==0)
				mid++;
			/*
			 * find the first non-emptyp string to the left,
			 * if all the strings on the left are empty, mid1 will end up with
			 * smaller than left(out of bound)
			 */
			while(mid1>=left && arr[mid1].trim().length()==0)
				mid1--;
			//if both pointers are out of bound, target not found
			if(mid>right && mid1<left)
				return -1;
			else if(mid<=right && mid1>=left){
				int difLeft = t.compareTo(arr[mid1]);
				int difRight = t.compareTo(arr[mid]);
				if(difLeft==0)
					return mid1;
				if(difRight==0)
					return mid;
				if(difLeft>0 && difRight>0)
					left = mid+1;
				else if(difLeft<0 && difRight<0)
					right = mid1-1;
				else if(difLeft>0 && difRight<0){
					right = mid-1;
					left = mid1+1;
				}else{
					throw new IllegalArgumentException("The given array is not in ascending order.");
				}
			}else if(mid<=right){	//no left
				int dif = t.compareTo(arr[mid]);
				if(dif==0)
					return mid;
				if(dif>0)
					left = mid+1;
				else
					right = mid-1;
			}else{		//no right
				int dif = t.compareTo(arr[mid1]);
				if(dif==0)
					return mid1;
				if(dif>0)
					left = mid1+1;
				else
					right = mid1-1;
			}
		}
		return -1;
	}

Clap

Clap