Goals: Using arrays and functions, searching arrays Problem: Modify the Lab10_te

Question

Goals: Using arrays and functions, searching arrays

Problem: Modify the Lab10_template.cpp file to contain a function that will search the array for a value using the Binary Search method. The file given to you contains the Lab 9 solution, which stops on a negative value. All positive numbers would be put into the array.

First, edit the function that inputs values into the array: remember that the array must be ordered! Your function should check that each number entered is larger than the previous number. Test this function a few times to make sure it works. When the array is printed, make sure it is in the correct order on the screen.

Now write the function for the binary search. The function should return the position of the element found, if applicable. You may use the binary search code given to you in lecture.

Your modified code should have 3 functions (one to input values into the array, one to print the array, and one to search the array). Your main function should call the function to input elements into the array, call the function to print the contents of the array, call the function to search the array, and then print the location of the found element (if applicable). If the element was not found in the array, then there should be a printout to indicate that.


template
/* Program that utilizes a function to input positive numbers in an array and
another function to output the array elements. The main function will declare
an array to contain a mazimum of 100 elements, call the function for input, then
call the function to print. Input of numbers into the array will stop when a
negative number has been entered.

input: numbers into an array
output: the numbers that were stored in the array
processing: loops are used for both input and output functions
*/



#include <iostream>
using namespace std;
int Function1(double []);
void PrintArray(const double [], int);
int BinarySearch(const double[] , int, double);

const int MAXSIZE = 100;
int main()
{
double array1[100];
int count;
double key;
count = Function1(array1);
cout<<"There were "<<count<<" numbers entered into the array."<<endl;

PrintArray(array1,count);

BinarySearch(array1, count,key);
cout<<key<< "found at " <<;
return 0;
}


//Function to input positive numbers into an array. The function accepts the array,
//utilizes a loop that will stop when a negative number or 100 values have been entered,
//then returns the numbers of values that were entered.
//PRE: An array with maximum number of elements of 100 has been declared
//POST: Positive values have been stored in the array and number of values has been
// returned.
int Function1(double fntArray[])
{
int i = 0;
double somenumber;
do
{
cout<<"Please enter a number to enter into the array or a negative number to stop."<<endl;
cin>>somenumber;
if (somenumber >= 0 && somenumber >= fntArray[i-1])
{
fntArray[i] = somenumber;
i++;
}
} while (i < MAXSIZE && somenumber >= 0 && somenumber >= fntArray[i-1]);

return i;
}

//Function to print out the contents of a double array.
//Function will accept a double array and the number of elelments to be printed.
//A loop is used to print the contents
//PRE: Array has been declared and filled
//Post: The contents of the array have been displayed on screen
void PrintArray(const double a1[], int size)
{
for(int i = 0; i < size; i++)
{
cout<<a1[i]<<endl;
}
}
// binary search code
int BinarySearch(const double a[ ], int size, double key)
{
int high = size-1, low = 0, middle;
cout <<" enter number needed to be found:" ;
cin >> key;
while (low <= high)
{
middle = (low + high)/2;
if (key == a[middle])
{
return middle;
}
else if (key < a[middle])
{
high = middle - 1 ;
}
else
{
low = middle + 1 ;
}

return -1;
}
}

Explanation / Answer

1.You can not use binary search on unsorted arrays. I wrote two functions for you, one that sorts the array, the other is the bs implementation. Binary search first checks if the element that you are looking for is in the middle, if not it checks if the element is larger or smaller. If for example the value you are looking for is smaller than in the middle then the BS knows it does not have to search the high part of the array and thus cutting the search area in half, until found or not found. void SortArray(double arr[],int length) { double temp; for(int i = 0;i

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

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