There is only one problem this time, but it is worth 25 points.
Read the material on binary search in the articles by Jon Bentley that I handed out very carefully. Write and test an iterative binary search procedure in the language of your choice. The object is not to show cleverness in the use of the particular language, but to make the correctness of the procedure extremely clear and convincing. The correspondence of the actual program to a program in the idealized assignment, conditional, iteration language that we have been studying must also be very clear. Use a loop invariant to help derive and present your procedure.
The programming problem is merely to determine whether or not a particular value T is present in the array X[1..N]. You are not required to point to the value, nor to the place where it should be inserted (although that is a very interesting extension that you might look into on another occasion). Don't get carried away with the idea of breaking out of the loop as soon as the value T is found. The most elegant solutions don't do so. The efficiency benefits are at best tiny, and unless you code extremely carefully, the cleverer program is likely to be slower rather than faster than the simpler one.
All of the information that you need may be found in the Bentley papers, but you must condense that information to the most efficient possible convincing presentation of a correct procedure. Notice that I ask for an efficient presentation of a correct procedure. A beautiful presentation in one or two pages is feasible. You may choose the combination of discussion embedded as comments in the program vs. separate presentation of discussion that you find clearest. With care, you can do even better than Bentley.
The choice of invariant is one key to success. Several different invariants will work, but the one you choose must mesh perfectly with your programming techniques. The initial presentation by Bentley suggests
If T is in the array X[1..N], then it is in X[L..U]Another possibility (my favorite) is
(X[I]<T for all I s.t. 1<=I<=L) and (X[J]>=T for all J s.t. U<=J<=N)There are a number of variations on the second version, depending on the use of strict or nonstrict comparisons at various places in the assertion. One of these variations is equivalent to Bentley's version (given the assumption that X[1..N] is sorted). The precise meanings of L and U are different in each version, leading to different initializations and different loop conditions.
You may use mathematical notation, English, and/or pictures to present preassertions, invariants, and any other assertions, as long as your presentations are completely precise and unambiguous. Both of the examples above are sufficiently precise. The biggest danger is in pictures. If you use pictures (which can work very well if you do it right), you must make it clear precisely what values of variables are presented by any arrows that you draw. The examples on pages 83-84 and in problems 3.11 and 3.12 on pages 97-99 of the text are sufficiently precise, but notice that the crossed arrows in Figure 3.19 on page 98 describe a computation step, rather than an assertion about a single state. You may describe computation steps, but that must be in addition to presentation of invariants and any other crucial assertions, not instead of the pure assertions.