cc 9-5

package Question9_5;

import java.util.ArrayList;

public class Question {
    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;
            }
            // this part is redundant, the first while already gurantee this
            // case
            // would not happen. we can not completely depend on the book. they
            // made
            // mistakes sometimes.
            if (last < first) {
                return -1; // this block was empty, so fail
            }
            // bit operator, quicker than (last+first) / 2
            // to prevent overflow, you'd better use first + ( last - first ) /
            // 2
            int mid = (last + first) >> 1;
            // if mid is "", go right
            while (strings[mid] == "") {
                ++mid; // will always find one
            }
            // notice in java how to compare string
            int r = strings[mid].compareTo(str);
            if (r == 0)
                return mid;
            // if r < 0, means mid < str, need to go right half, to part of
            // mid+1->last
            if (r < 0) {
                first = mid + 1;
            }
            // else go to left half, to part of first->mid-1
            else {
                last = mid - 1;
            }
        }
        return -1;
    }

    public static int search(String[] strings, String str) {
        if (strings == null || str == null) {
            return -1;
        }
        // cornor case, need to be handled specificially
        // if I wrote it, I may forget to put such a check here
        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);
    }

    public static void main(String[] args) {
        String[] stringList = { "apple", "", "", "banana", "", "", "",
                "carrot", "duck", "", "", "eel", "", "flower" };
        for (String s : stringList) {
            System.out.println("<" + s + "> " + " appears at location "
                    + search(stringList, s));
        }
    }
}

notice : the above code, when meet “”, it would go to right, go to single direction. if we can go to both direction, it would speed up the searching process. the below code achieved this goal.

int binary_search_string(string *s, string sample, int left, int right){

    if(left > right) return -1;
    int mid = (left + right) / 2;

    if(s[mid] == sample) return mid;
    if(s[mid] == ""){
        int l = binary_search_string(s, sample, left, mid - 1);
        int r = binary_search_string(s, sample, mid + 1, right);
        if(l > 0) return l;
        else if( r > 0) return r;
        else return -1;
    }
    if(s[mid] > sample) return binary_search_string(s, sample, left, mid - 1);
    if(s[mid] < sample) return binary_search_string(s, sample, mid + 1, right);

}

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

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