package stringoperation;

public class SearchStringwithSpace {

    // CC150 11.5
    public static int searchI(String[] strings, String str, int first, int last) {
        while (first <= last) {
        /* Move mid to the middle */
            int mid = (last + first) / 2;

	    /* If mid is empty, find closest non-empty string */
            if (strings[mid].isEmpty()) {
                int left = mid - 1;
                int right = mid + 1;
                while (true) {
                    if (left < first && right > last) {
                        return -1;
                    } else if (right <= last && !strings[right].isEmpty()) {
                        mid = right;
                        break;
                    } else if (left >= first && !strings[left].isEmpty()) {
                        mid = left;
                        break;
                    }
                    right++;
                    left--;
                }
            }

            int res = strings[mid].compareTo(str);
            if (res == 0) { // Found it!
                return mid;
            } else if (res < 0) { // Search right
                first = mid + 1;
            } else { // Search left
                last = mid - 1;
            }
        }
        return -1;
    }

    public static int searchR(String[] strings, String str, int first, int last) {
        if (first > last) {
            return -1;
        }

	/* Move mid to the middle */
        int mid = (last + first) / 2;

	/* If mid is empty, find closest non-empty string. */
        if (strings[mid].isEmpty()) {
            int left = mid - 1;
            int right = mid + 1;
            while (true) {
                if (left < first && right > last) {
                    return -1;
                } else if (right <= last && !strings[right].isEmpty()) {
                    mid = right;
                    break;
                } else if (left >= first && !strings[left].isEmpty()) {
                    mid = left;
                    break;
                }
                right++;
                left--;
            }
        }

	/* Check for string, and recurse if necessary */
        if (str.equals(strings[mid])) { // Found it!
            return mid;
        } else if (strings[mid].compareTo(str) < 0) { // Search right
            return searchR(strings, str, mid + 1, last);
        } else { // Search left
            return searchR(strings, str, first, mid - 1);
        }
    }

    public static int search(String[] strings, String str) {
        if (strings == null || str == null || str.isEmpty()) {
            return -1;
        }
        return searchR(strings, str, 0, strings.length - 1);
    }

    public static void main(String[] args) {
        String[] stringList = {"apple", "", "", "banana", "", "", "",
                "carrot", "duck", "", "", "eel", "", "flower"};
        System.out.println(search(stringList, "ac"));

        // for (String s : stringList) {
        // String cloned = new String(s);
        // System.out.println("<" + cloned + "> " + " appears at location " +
        // search(stringList, cloned));
        // }
    }

}
