cc 9-3

package Question9_3;

public class Question {

    public static int search(int a[], int l, int u, int x) {
        while (l <= u) {
            int m = (l + u) / 2;
            if (x == a[m]) {
                return m;
            }
            // a[l] <= a[m], ascend from l->m
            else if (a[l] <= a[m]) {
                // x>a[m] then x > all element between l->m
                // so l = m+1
                if (x > a[m]) {
                    l = m + 1;
                }
                // if x >= a[l] but x < a[m]
                // the u = m-1
                else if (x >= a[l]) {
                    u = m - 1;
                }
                // if x < a[l], then it could not be any one of l->m
                // since we already know l->m is ascending, so we need
                // to go the upper half
                else {
                    l = m + 1;
                }
            }
            // pre-condition a[l] > a[m], then it loses monotonicity
            // from l->m it is not ascending, but another half(m->u) must
            // be in an ascending order, so a[m+1] > a[m]..
            else if (x < a[m])
                u = m - 1;
            // a[m]<x<=a[u], then goto another half of m->u
            else if (x <= a[u])
                l = m + 1;
            // x>a[u], nothing from m->u would satisfy, have to goto
            // l->m
            else
                u = m - 1;
        }
        return -1;
    }

    public static int search(int a[], int x) {
        return search(a, 0, a.length - 1, x);
    }

    public static void main(String[] args) {
        int[] a = { 4, 5, 6, 7, 8, 9, 1, 2, 3 };
        for (int x : a) {
            System.out.println(x + " is at position " + search(a, x));
        }
    }

}

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