Binary search on suffix array

Question

My code calculates the starting position of the intervall correctly but not the end position:

    int left;
    int bot = 0; int top = textLength;

    while(bot != top)
    {
        int mid = (bot+top)/2;

        if(pattern.compareTo(text.substring(suffixArray.get(mid))) > 0) bot = mid + 1;
        else top = mid;
    }

    left = bot;



    int right;
    bot = left; top = textLength;

    while(bot != top)
    {
        int mid = (bot+top)/2;

        if(pattern.compareTo(text.substring(suffixArray.get(mid))) < 0) top = mid;
        else bot = mid+1;
    }

    right = bot;

I compared it to several pseudo codes on the internet and I don't really see why it's not working. What am I missing?

Answer 1

The search for right differs only in >= instead of >

    if(pattern.compareTo(text.substring(suffixArray.get(mid))) >= 0) bot = mid + 1;
    else top = mid;

So I would think

right = bot;

to point to the next higher value.

So better check first whether all is ordered:

String old = text.substring(suffixArray.get(0));
for (int i = 1; i < textLength; ++i) {
    String next = text.substring(suffixArray.get(i));
    if (old.compareTo(next) >= 0) {
        System.err.printf("Wrong order at [%d] '%s' >= [%d] '%s'%n",
            i - 1, old, i, next);
    }
    old = next;
}