On Jul 10, 6:38*pm, pete <(E-Mail Removed)> wrote:

> Juha Nieminen wrote:

> > Ray Leon wrote:

> >> I have completed a quiz and just want feedback on any possible mistake I

> >> have made if any. Any help is greatly appreciated. I think I have the

> >> correct answers for the following questions:

>

> >> 1. Let myArray represents an array of 5 elements with the following values

> >> in this order: 10, 20, 30, 40, 50. How many comparisons does it take to find

> >> the element 30 (the third element) using:

>

> >> a. Sequential search (10 points)

>

> >> b. Binary search (10 points)

>

> >> Answer below:

>

> >> Sequential search - Three (3)

>

> >> Binary search - One (1)

>

> > * The answer may not be that simple because "binary search" is not a

> > completely unambiguous term. More precisely, you have to state what

> > happens if the binary search is performed on an array which may contain

> > repeated values: Should the binary search just tell whether the element

> > exists in the array, or if there's more than one such element, should it

> > return a handle to the first one in the array?

>

> > * If "binary search" means "tell me if this element exists in the

> > array", then the answer of 1 is correct. However, if it means "give me a

> > handle to the first appearance of this element in the array", then the

> > correct answer becomes 3 (because the binary search needs to be

> > continued even if an element with the same value is found immediately).

>

> >> 2. Consider the array consisting of 7 elements sorted in ascending order.

> >> What is the Maximum number of comparisons that need to be done to find any

> >> given element using:

>

> >> a. Sequential search (10 points)

>

> >> b. Binary search (10 points)

>

> >> Answer below:

>

> >> Sequential search - Seven (7)

>

> >> Binary search - *Two (2)

>

> > * Even if we are only checking for the existence of the element in the

> > array, the binary search would require in the worst case 4 comparisons:

> > the first comparison checks the fourth element, then, assuming that

> > element is too small, it checks the fifth element (because the middle of

> > 4 and 7 is 5.5, which gets rounded eg. to 5), then assuming that one is

> > also too small, it checks the sixth element (which is the middle of 5

> > and 7), and if that also was too small, finally the seventh.

>

> That is wrong.

> If it were element 7,

> the binary search pattern would be 4,6,7.

>

> Incrementing from 4 to 7,

> just obviously isn't binary search.

>

> /* BEGIN new.c output */

>

> int array[] = {1,2,3,4,5,6,7};

>

> Searching for value 1 in array.

> Value 1, found in array[0].

> 3 comparisons were made.

>

> Searching for value 2 in array.

> Value 2, found in array[1].

> 2 comparisons were made.

>

> Searching for value 3 in array.

> Value 3, found in array[2].

> 3 comparisons were made.

>

> Searching for value 4 in array.

> Value 4, found in array[3].

> 1 comparisons were made.

>

> Searching for value 5 in array.

> Value 5, found in array[4].

> 3 comparisons were made.

>

> Searching for value 6 in array.

> Value 6, found in array[5].

> 2 comparisons were made.

>

> Searching for value 7 in array.

> Value 7, found in array[6].

> 3 comparisons were made.

>

> /* END new.c output */

>

> /* BEGIN new.c */

>

> #include <stdio.h>

>

> #define NMEMB(A) * * * *(sizeof(A) / sizeof *(A))

>

> int Comps;

>

> void *b_search(const void *key, const void *base,

> * * * * * * * * size_t nmemb, size_t size,

> * * * * * * * * int (*compar)(const void *, const void *));

> int comparison(const void *arg1, const void *arg2);

>

> int main(void)

> {

> * * *int array[] = {1,2,3,4,5,6,7};

> * * *const int target[] = {1,2,3,4,5,6,7};

> * * *unsigned index;

> * * *int *found;

>

> * * *puts("/* BEGIN new.c output */\n");

> * * *puts("int array[] = {1,2,3,4,5,6,7};\n");

> * * *for (index = 0; index != NMEMB(target); ++index) {

> * * * * *Comps = 0;

> * * * * *printf("Searching for value %d in array.\n", target[index]);

> * * * * *found = b_search(target + index, array, NMEMB(array)

> * * * * * * *, sizeof*array, comparison);

> * * * * *if (found != NULL) {

> * * * * * * *printf("Value %d, found in array[%u].\n"

> * * * * * * * * *"%d comparisons were made.\n"

> * * * * * * * * *, target[index]

> * * * * * * * * *, found - array, Comps);

> * * * * *} else {

> * * * * * * *printf("Value %d, not found in array.\n"

> * * * * * * * * *"%d comparisons were made.\n"

> * * * * * * * * *, target[index], Comps);

> * * * * *}

> * * * * *putchar('\n');

> * * *}

> * * *puts("/* END new.c output */");

> * * *return 0;

>

> }

>

> void *b_search(const void *key, const void *base,

> * * * * * * * * size_t nmemb, size_t size,

> * * * * * * * * int (*compar)(const void *, const void *))

> {

> * * *int comp;

> * * *size_t middle, high, low;

> * * *const unsigned char *array, *found;

>

> * * *found = NULL;

> * * *if (nmemb != 0) {

> * * * * *array = base;

> * * * * *low = 0;

> * * * * *high = nmemb;

> * * * * *do {

> * * * * * * *nmemb = high - low;

> * * * * * * *middle = nmemb / 2 + low;

> * * * * * * *base = middle * size + array;

> * * * * * * *comp = compar(key, base);

> * * * * * * *if (comp > 0) {

> * * * * * * * * *low = middle;

> * * * * * * *} else {

> * * * * * * * * *high = middle;

> * * * * * * * * *if (comp == 0) {

> * * * * * * * * * * *found = base;

> * * * * * * * * * * *break;

> * * * * * * * * *}

> * * * * * * *}

> * * * * *} while (nmemb != 1);

> * * *}

> * * *return (void *)found;

>

> }

>

> int comparison(const void *arg1, const void *arg2)

> {

> * * *++Comps;

> * * *return *(const int *)arg2 *> *(const int *)arg1 ? -1

> * * * * * : *(const int *)arg2 != *(const int *)arg1;

>

> }

>

> /* END new.c */

>

> --

> pete

2. Consider the array consisting of 7 elements sorted in ascending

order. What is the Maximum number of comparisons that need to be done

to find any given element using:

a. Sequential search (10 points)

b. Binary search (10 points)

Answer below:

a. Since the total number of elements is seven, and the value is

unknown I can only assume that the maximum number of comparisons may

be the total amount of elements, seven (7).

b. The binary search for any given number is what I can’t figure out.

I have attempted to use the following code and formula but am very

confused as to what the answer could be. I can get certain values but

when I try for example the number two as the value to search for it

just doesn’t work.

low = 0

high = N

while (low < high) {

mid = (low + high)/2;

if (A[mid] < value)

low = mid + 1;

else

//can't be high = mid-1: here A[mid] >= value,

//so high can't be < mid if A[mid] == value

high = mid;

}

if (low < N) and (A[low] == value)

return low

else

return not_found

any help greatly appreciated.