Find minimum singular value in a sorted array

A sorted array is passed to my method and i have to find the minimum singular value. If no such value is found the method returns 0.
I have created two versions of this method. In the first version, I iterate trough the array twice which works fine but there has to be a way to find the value with one iteration.
In the second version, I iterate through it once but i need it fixed so, that it works if the last index of the array is my minimum singular value e.g {1, 1, 2, 2, 3}.

//First version with two iterations
public int findMinimumSingularValue(int[] array) {

    for (int i = 0; i < array.length; i++) {
        int countOccurence = 0;
        for (int j = 0; j < array.length; j++) {
            if (array[i] == array[j]) {
                countOccurence ++;
            }
        }
        if(countOccurence == 1) {
            return array[i];
        }
    }
    return 0;
}

I've tried to implement it with only one iteration, but couldn't get it to work. Only the first version is up for review, but I'll leave my attempt at improvement here to illustrate what I have in mind:

//Second version with one iteration which needs to be fixed
public int findMinimumSingularValue(int[] array) {
    if(array.length == 0) {
        return 0;
    }
    int isNotUnique = array[array.length - 1];
    for (int i = 0; i < array.length; i++) {
        if (array[i] != array[i + 1] && array[i] != isNotUnique) {
            return array[i];
        }
        isNotUnique = array[i];
    }
    return 0;
}

for (int i = 0; i < array.length; i++) {
        int countOccurence = 0;
        for (int j = 0; j < array.length; j++) {
            if (array[i] == array[j]) {
                countOccurence ++;
            }
        }
        if(countOccurence == 1) {
            return array[i];
        }
    }
    return 0;

When I look at this, the problem that I see is that you are scanning the entire array to look for duplicates. The array is sorted! Consider

int i = 0;
    while (i + 1 < array.length) {
        // array[i] has a duplicate iff it is the same as array[i + 1]
        if (array[i] != array[i + 1]) {
            return array[i];
        }

        // skip to the next possible smallest value not a duplicate
        while (i + 1 < array.length && array[i] == array[++i]) ;
    }

    // figure out if the last element has no duplicate
    return (array.length == 0 || array[i] == array[i - 1]) ? 0 : array[i];

While it may look like it has nested loops, both iterate over the same variable. So the number of comparisons is linear relative to the size of the array.

This works because the array is sorted. All duplicates are adjacent to each other.

The ++i increments i and then returns the now incremented value. i++ stores the value of i, then increments it, and finally returns it. So i++ + 1 is the same thing as ++i. Or vice versa.

class Incrementable {

    private int i = 0;

    // ++i
    public int preincrement() {
        i = i + 1;
        return i;
    }

    // i++
    public int postincrement() {
        int original = i;
        i = i + 1;
        return original;
    }

}

The two forms ++i and i++ are the equivalents of the preincrement and postincrement in this class.

So let's go through

while (i + 1 < array.length && array[i] == array[++i]) ;

The form

while (isTrue()) ;

just keeps iterating until isTrue returns false. It does nothing in the body of the loop, thus the empty ;. We could also write it

while (isTrue()) {

}

But that just seems longer.

The i + 1 < array.length just keeps us from falling off the back of the array. I.e. we never want to do array[array.length], as that's an error (attempt to access outside the array).

So the meat of the statement is the array[i] == array[++i]. On any particular iteration, this is just the same as array[i] == array[i + 1]. So long as that is true, we're still processing the same duplicate. But replacing i + 1 with ++i has the same effect on an individual iteration and moves along. So we have something like an array of


1, 1, 2, 2, 2, 2, 3

i = 0, array[i] = 1, array[++i] = 1, i = 1; equal so keep going

i = 1, array[i] = 1, array[++i] = 2, i = 2; not equal so stop and do the outer while

i = 2, array[i] = 2, array[++i] = 2, i = 3; equal so keep going

i = 3, array[i] = 2, array[++i] = 2, i = 4; equal so keep going

i = 4, array[i] = 2, array[++i] = 2, i = 5; equal so keep going

i = 5, array[i] = 2, array[++i] = 3, i = 6; not equal so stop and do the outer while

While i is 6, we'll drop out of the inner loop and the outer loop, because 6 + 1 is not less than array.length, which is 7.

StackExchange Code Review Q#159971, answer score: 5