CODEWITHSUNDEEP
algorithm
McLovin
McLovin

Reputation: 3415

Find k in a k-sorted array

I'm trying to write a binary-search-like algorithm to find k in a k-sorted array. (It needs to be O(logn))

For example, k here is 3: 5, 6, 7, 1, 2, 3, 4

Here's my try in Java

public static int findk(int[] a) {
    int low = 0;
    int high = a.length-1;

    while(low <= high) {
        if(a[low] <= a[high])
            return low;

        int middle = (low+high)/2;
        if(a[low] > a[middle])
            high = middle-1;
        else
            low = middle+1;
    }

    return 0;
}

It works for some inputs but doesn't work for others. It should be really easy but I can't figure out what's wrong.

Even a hint will be nice!

Upvotes: 1

Views: 592

Answers (1)

maraca
maraca

Reputation: 8858

You need to find the first element which is smaller than a[0]. So you need to compare against a[0].

public static int findk(int[] a) {
    int low = 0;
    int high = a.length - 1;
    if (a[high] >= a[0]) // special case array completely sorted
        return high + 1;
    while(low < high) {
        int middle = (low + high) / 2;
        if(a[middle] < a[0])
            high = middle;
        else
            low = middle + 1;
    }    
    return low; // or high
}

You will get [0,6] on start, then [0,3], then [2,3] and finally [3,3].

The reason why we don't do high = middle - 1 is that this way we could end up in the k-values which we don't want.

Upvotes: 1

Related Questions