Could someone please help me with this assignment? Exercise 1: The variable midd

Question

Could someone please help me with this assignment?

Exercise 1: The variable middle is defined as an integer. The program contains the assignment statement middle=first+(last-first)/2. Is the right side of this statement necessarily an integer in computer memory? Explain how the middle value is determined by the computer. How does this line of code affect the logic of the program? Remember that first, last, and middle refer to the array positions, not the values stored in those array positions.

Exercise 2: Search the array in the program above for 19 and then 12. Record what the output is in each case.

Note that both 19 and 12 are repeated in the array. Which occurrence of

19 did the search find?

Which occurrence of 12 did the search find?

Explain the difference.

Exercise 3: Modify the program to search an array that is in ascending order.

Make sure to alter the array initialization.

// This program demonstrates a Binary Search

#include<iostream>
using namespace std;

int binarySearch(int [], int, int); // function prototype

const int SIZE = 16;

int main()
{
int found, value;
int array[] = {34,19,19,18,17,13,12,12,12,11,9,5,3,2,2,0}; // array to be searched

cout << "Enter an integer to search for:" << endl;
cin >> value;

found = binarySearch(array, SIZE, value); //function call to perform the binary search
//on array looking for an occurrence of value
if (found == -1)
cout << "The value " << value << " is not in the list" << endl;
else
{
cout << "The value " << value << " is in position number "
<< found + 1 << " of the list" << endl;
}
return 0;
}


//*******************************************************************
// binarySearch
//
// task: This searches an array for a particular value
// data in: List of values in an orderd array, the number of
// elements in the array, and the value searched for
// in the array
// data returned: Position in the array of the value or -1 if value
// not found
//
//*******************************************************************
int binarySearch(int array[],int numElems,int value) //function heading
{
int first = 0; // First element of list
int last = numElems - 1; // last element of the list
int middle; 0 // variable containing the current
// middle value of the list

while (first <= last)
{
middle = first + (last - first) / 2;

if (array[middle] == value)
return middle; // if value is in the middle, we are done

else if (array[middle]<value)
last = middle - 1; // toss out the second remaining half of
// the array and search the first
else
first = middle + 1; // toss out the first remaining half of
// the array and search the second
}

return -1; // indicates that value is not in the array
}

Explanation / Answer

1 E)

The right side of the statement should be an integer only. As we are checking array[middle] is less than or greater than value, the index of an array(middle) should be an integer, if it is a float number then error will araise.

The middle value is determined by addition of first to the result( which is calculated as the difference of last and first and then divided by 2).

example: first = 0, last = 14, then middle = ( 0 + (14 - 0 ) / 2 ) = 0 + 14 / 2 = 0 + 7 = 7

Each time when the array[middle] is mismatched with value, the first or last is updated with new value. Since the array is in Sorted order, for each iteration the size of the array is divided in to half.

Suppose we are searching for 5

{34,19,19,18,17,13,12,12,12,11,9,5,3,2,2,0}

Now searching is between from 0 th index to 10 th index.

// Iteration 1

middle = 0 + (15 - 0)/2 = 7

array[middle] = 12

comparing with the array[middle] with the value (5),

As array[middle] is greater than value // else condition

first is updated to middle + 1

That is first is updated to 8.

Now searching is between from 8 th index (first) to 15 th index (last) .

// Iteration 2

middle = 8 + (15 - 8) / 2 = 8 + 3 = 11

array[middle] = 2

comparing with the array[middle] with the value (5),

As array[middle] is less than value // else if condition

last is updated to middle - 1

That is last is updated to 11 - 1 = 10.

Now searching is between from 8 th index (first) to 10 th index(last).

Like wise, in each iteration by changing the middle value the space to search the value is reduced by half.

--------------------------------------------------------------------------------------------------------------------------------------------------

2)

The occurrence of 19 is at 1 st index.

In first iteration, middle is 7 and value is 12

In second iteration, middle is 3 and value is 18

In third iteration, middle is 1 and value is 19

Since array[middle] is matches with value, the search ends in third iteration.

The occurrence of 12 is at 7 th index.

In the first iteration, middle = 0 + (15 - 0)/2 = 7

Since array[middle] is matches with value, the search ends in first iteration.

----------------------------------------------------------------------------------------------------------------------------------------

3)

#include<iostream>
using namespace std;

int binarySearch(int [], int, int); // function prototype

const int SIZE = 16;

int main()
{
int found, value;
int array[] = {0,2,2,3,5,9,11,12,12,12,13,17,18,19,19,34}; // array to be searched

cout << "Enter an integer to search for:" << endl;
cin >> value;

found = binarySearch(array, SIZE, value); //function call to perform the binary search
//on array looking for an occurrence of value
if (found == -1)
cout << "The value " << value << " is not in the list" << endl;
else
{
cout << "The value " << value << " is in position number "
<< found + 1 << " of the list" << endl;
}
return 0;
}

Binary Search:

int binarySearch(int array[],int numElems,int value) //function heading
{
int first = 0; // First element of list
int last = numElems - 1; // last element of the list
int middle; 0 // variable containing the current
// middle value of the list

while (first <= last)
{
middle = first + (last - first) / 2;
if (array[middle] == value)
return middle;
else if (array[middle]>value)
last = middle - 1;
else
first = middle + 1;
}

return -1;

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.