Binary Search Algorithm
<pre><code>public class firstPosition {

// Pre-condition: the array a is in ascending order.
//
// Specification:
//
// We calculate and return the number s such that:
//
// a[i] &lt;  x for all indices i &lt;  s, and
// a[i] &gt;= x for all indices i &gt;= s.
public int firstPosition(int x, int[] a) {

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

    while (lower != upper) {
        // invariant: 0 &lt;= lower &lt;= s &lt;= upper &lt;= a.length
        int mid = (lower + upper) / 2;
        assert (lower &lt;= mid &amp;&amp; mid &lt; upper);
        if (x &lt;= a[mid]) {    // s &lt;= mid
            upper = mid;
        } else {              // mid &lt; s
            lower = mid + 1;
        }
    }
    return (lower);

    // Jutification of correctness:
    //
    // Because lower == upper is the negation of the while-loop condition,
    // we conclude that lower == s == upper, by the invariant.
}
public static void main(String[] args) {
    firstPosition(1);
}
}
</code></pre>

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

<ol>
<li>x = 3</li>
<li>x = 4</li>
<li>x = 5</li>
<li>x = 9</li>
<li>x = 11</li>
</ol>

<p>How many times is the loop body executed as a function of the length of the given array?</p>

<p>I have tried executing the code in the compiler, however I get an error at the method call. Please could you give me advice on how to answer this question and get the code to compile correctly?</p>
