1. (a) Yes.  Given any d+1 points on a polynomial p(x) of degree
at most d, you can uniquely recover p(x).  (This is valid for the
real numbers.)
(b) No.  The x-values just have to be distinct.  It doesn't matter
what four x-values I choose.
(c) Yes, if p(x) has degree 4, you need 5 points to recover p(x);
4 points are not enough.

2. 
public static int bsearch(int[] A, int v) {
    int l=0, r=A.length;
    while (l < r) {
        int midpoint = l + (r-l)/2;
        /* Invariant: v appears in A if and only if v appears in A[l..r-1]. */
        /* Invariant: l <= midpoint < r */
        if (A[midpoint] < v)
            l = midpoint+1;
        else if (A[midpoint] > v)
            r = midpoint;
        else
            return midpoint;
        /* Invariant: v appears in A if and only if v appears in A[l..r-1]. */
        /* Invariant: the value of r-l here is strictly smaller than its
           value at the beginning of this loop iteration. */
    }
    return -1;
}

I have annotated the code with invariants that suffice to see why
this code never returns an correct answer, and why it is guaranteed
to terminate (i.e., it cannot enter an infinite loop).

Many of your answers contained small mistakes.  Here is a sampling
of some of the errors I saw:
 * Initializing r to "A.length-1" instead of "A.length"
   (works incorrectly on an array of length 1)
 * Setting r to "midpoint-1" instead of "midpoint"
   (may work incorrectly when the value v appears just to the left of midpoint)
 * Setting l to "midpoint" instead of "midpoint+1"
   (may cause the algorithm to enter an infinite loop in some cases, e.g.,
   on an array of length 1 whose only element is smaller than v)
 * Misreading "l" (the letter l) as "1" (the number one) -- OK,
   this was more my fault for choosing a variable name that could
   be misread in this way.
 * Returning the wrong thing when the value v was found at midpoint.
 * Copying the entire array (or half of it) into a new array
   (takes longer than O(lg n) time).

If you had an off-by-one error, don't feel bad: you're in good company.
In his book "Programming Pearls", programming guru Jon Bentley describes
an experiment where he asked a room full of professional programmers to
implement binary search.  He found that 90% had bugs in their code.  He
argues that a systematic use of invariants can help you avoid these kinds
of bugs.

P.S. Why did I write "midpoint = l + (r-l)/2" instead of
"midpoint = (l+r)/2"?  It's a very subtle and minor issue, but here is why:

http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

If it's any consolation, even the binary search algorithm printed in
Bentley's book had a bug that wasn't discovered until 20 years later!