Java firstPosition Algorithm

int firstPosition(int x, int [] a) {

    int lower = 0;
    int upper = a.length;

    while (lower != upper) {
    int mid = (lower + upper) / 2;

    **if (x <= a[mid]) {** // the line I don't understand
    upper = mid;
 开发者_C百科   } else {
    lower = mid + 1;
    }
    return (lower);
}

If a = {4, 4, 5, 5, 6, 7, 8, 9, 9, 9} what will the algorithm return for the following choices of x?

i) x = 3

ii) x = 4

iii) x = 5

iv) x = 9

v) x = 11

I have tried stepping through this program, for example x = 3, a.length returns 10, so upper is always equal to 10.

while ( 3 ! = 0 ) { // execute line

int mid = lower + upper / 2 - which is (0 + 10)/2 = 5

if ( x <= a[mid]) // I assume that means if 3 is less than or equal to 5? 5 then replace mid with 5 and then...

lower = mid + 1 // 5+1 = 6, return 6 as lower?

This is a basic binary search algorithm, implemented iteratively instead of recursively.

The line you don't understand checks to see if x (the search value) might lie in the lower half or upper half of the array. This works because the array is sorted. We can divide any sorted array into two halves, and look at the value in the middle to determine which half the value we're looking for might be in.

Say that the array looks like this:

+---+---+---+---+---+----+
| 1 | 3 | 5 | 7 | 9 | 11 |
+---+---+---+---+---+----+
  ^                        ^
  |                        |
lower                    upper

and we're trying to figure out which slot the number 9 is in. Since the array is sorted, we can immediately discard half of the array.

How?

Look at the value in the "center" of the array: it's 5, and 9 is larger than 5, so we know that 9 must be in the upper half of the array. Algorithmically speaking, this would be the else case of the if statement in your code.

So we repeat the same process, but only looking at the upper half of the array this time:

+---+---+---+---+---+----+
| 1 | 3 | 5 | 7 | 9 | 11 |
+---+---+---+---+---+----+
              ^            ^
              |            |
            lower        upper

Looks to me like a binary search algorithm. The choice of x makes sure that the array part that needs to be searched is halved each iteration. Read more about it here

This is a modification of a binary search.

Since the data is ordered, to determine if you can throw away the "upper" or "lower" half of a range of data, look at the middle element. When it is bigger than the number you're looking for, you can safely throw away the numbers past it (by reducing the range). When it is smaller than the number you are looking for, you can safely throw away the numbers before it (by reducing the range).

The key here is that if it is the number you are looking for, you need to crawl back towards the beginning of the range until you detect that the "next" number is not actually the "first" of that possibly repeated value.