Homework Assignment #6 cse 452: Fall 2004 Due: 11/23/04 Instructions

1. 
   (6.21) Given the following description for binary search:
   

[Bentley] “We are to determine whether the sorted array X[1..N] contains the element T. Binary search solves the problem by keeping track of a range within the array in which T must be if it is anywhere in the array. Initially, the range is the entire array. The range is shrunk by comparing its middle element to T and discarding half the range. The process continues until T is discovered in the array or until the range in which it must lie is known to be empty.”

1. 
   In your favorite programming language, write the code to produce the binary search according to the above requirements:
   

bool binarySearch (int X[], int N, int T)

{
int first = 0;

int last = N – 1;

int position;

position = (last + first) / 2;

while( first <= last && X[position] != T)

{

if(X[position] > T) last = position - 1;

position = (last + first) / 2;

}
if(first <= last) return true;

return false;

}

2. 
   What looping construct was the most useful for your program?
   

The while loop.

3. 
   Give the loop invariant(s) for your solution (indicate where you placed the invariant(s))?
   

The invariant is first <= last which was placed in a pretest position.

2. 
   (8.8) Write (in a language of your choice) a function or a procedure that will produce 4 different effects depending on whether the parameters are passed by value, by reference, by value-result, or by name.
   

int main ( )

{

int a = 1;

int w = 3;

int z = 4;

foo( a, b);

print( a, b); // by value prints 1 5

foo( &a, &b);

print( a, b); // by reference prints 6 5
foo( inout a, inout b);
print( a, b); // by value-result prints 6 5
foo (name w, name z);

print( a , b); // by name prints 7 4

}
void foo (int x, int y)

{

x = x + y;

3. 
   (8.16) Why do you suppose that variable-length argument lists are so seldom used in high-level programming languages?