Jedore Jedore -4 years ago 80
C Question

binary search in Data Structure and Algorithm Analysis in C

When addressed the Binary_Search in chapter 2(2.4.4),the author mentioned that
"


Notice that the variables cannot be declared unsigned(why?).In cases
where the unsigned qualifier is questionable, we will not use it. As
an example, if the unsigned qualifier is dependent on an array not
beginning at zero, we will discard it. we will not use it. As an
example, if the unsigned qualifier is dependent on an array not
beginning at zero, we will discard it. We will also avoid using the
unsigned type for variables that are counters in a for loop, because
it is common to change the direction of a loop counter from increasing
to decreasing and the unsigned qualifier is typically appropriate for
the former case only. For example, the code in Exercise 2.10 does not
work if i is declared unsigned.
".


The code as follow:

int binary_search( input_type a[ ], input_type x, unsigned int n )
{
int low, mid, high; /* Can't be unsigned; why? */
/*1*/ low = 0; high = n - 1;
/*2*/ while( low <= high )
{
/*3*/ mid = (low + high)/2;
/*4*/ if( a[mid] < x )
/*5*/ low = mid + 1;
else
/*6*/ if ( a[mid] < x )
/*7*/ high = mid - 1;
else
/*8*/ return( mid ); /* found */
}
/*9*/ return( NOT_FOUND );
}


Q:
I can't understand that the variable cannot be declared unsigned.Why the unsigned qualifier is questionable? And how does unsigned qualifier change the direction of a loop counter from increasing to decreasing?

Answer Source

If mid is 0, you want the line high = mid - 1; to set high to -1, which will cause the loop to stop.

If the variables were unsigned, high would wrap around to the maximum unsigned value which would cause a read past the end of the buffer and a likely crash.

As for for loops which count down, the following loop will never end:

for (unsigned i = START_VAL; i >= 0; i--) {...}  //WRONG

Because i is unsigned, the condition i >= 0 will always be true.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download