2 
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;
    } 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?
Improve this question
1
  • It looks like binary search. If the middle element of array is greater, then it lowers mid. Commented May 27, 2011 at 19:15

3 Answers 3

Reset to default
3

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
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

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

Improve this answer

7 Comments

So if x = 3, does lower return 6?
lower is a variable, not a function/method, so it does not "return" anything,
Yes, because the array length equals 10, so mid equals 5. As 3 < 5, lower becomes mid+1. Thus lower becomes 6
How many times is the loop body executed as a function of the length of the array?
Sounds like homework now. @Paradox: What do you notice about the size of the "array" (i.e., what happens to upper - lower approximately) each loop iteration? That should give you a clue.
|
0

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.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.