Searching and Sorting Write a program that prompts the user to enter the number
ID: 3862235 • Letter: S
Question
Searching and Sorting
Write a program that prompts the user to enter the number of elements and the numbers themselves to be placed in an integer array that holds a maximum of 50 elements. The program should then prompt the user for an integer which will be searched for in the array using a binary search. Make sure to include the following step along the way:
-A sort routine must be called before the binary search. You may use either the selection sort or the bubble sort. However, the sort must be implemented in its own function and not in main.
-Next include a function called by main to implement the binary search.The ordered array produced by the sort should be passed to the search routine which returns the location in the sorted array of the sought value, or -1 if the value is not in the array.
-Add a value returning function that computes the mean of you data set. Recall that the mean is the sum of the data values divided by the number of pieces of data. Your program should output the size of the array entered, the array as entered by the user, the sorted array, the integer being searched for, the location of that integer in the sorted array (or an appropriate message if it is not in the array), and the mean of the data set.
-Modify your program so that the data is entered from a file rather than from the keyboard. The first line of the file should be the size of the integer array. The second line should contain the integer searched for in the data set. Finally, the array elements are to start on the third line. Make sure you separate each array element with a space. The output, as described in should be sent to a file.
Sample Output:
Please input the number of integer
5
Please input integer number 1
4
Please input integer number 2
8
Please input integer number 3
-2
Please input integer number 4
10
Please input integer number 5
7
Enter an integer to search for:
1
This array has 5 items.
The array entered by the user is
4 8 -2 10 7
The sorted array is as follows:
-2 4 7 8 10
The item searched is 1
The value 1 is not in the list
The mean of all the elements in the array is 5.4
Press any key to continue . . .
Explanation / Answer
Here is the below code for the above scenario:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stddef.h>
int get_num_of_ints(
const int* arr,
size_t r,
int N,
size_t* first,
size_t* count
);
int main()
{
int N;
int arr[]={1,1,2,3,3,4,4,4,4,5,5,7,7,7,7,8,8,8,9,11,12,12};
size_t r = sizeof(arr)/sizeof(arr[0]);
size_t first;
size_t count;
printf( " Please input the integer you would like to find. " );
scanf( "%d", &N );
int a = get_num_of_ints( arr, r, N, &first, &count );
if( a == -1)
printf( "%d has not been found. ", N );
else if(a >= 0){
printf( "The first matching index is %d. ", first );
printf( "The total number of instances is %d. ", count );
}
return 0;
}
int get_num_of_ints(
const int* arr,
size_t r,
int N,
size_t* first,
size_t* count)
{
int lo=0;
int m=0;
int hi=r-1;
int w=r-1;
if( N < arr[0] || arr[hi] < N ){
m = -1;
}
else{
while(lo <= hi){
m = (hi + lo)/2;
if(arr[m] < N)
lo = m+1;
else if(arr[m] > N)
hi = m-1;
else if(arr[m]==N){
m=m;
break;
}
}
if (lo > hi)
m = -1;
}
if( m >= 0 ){
int j = m-1;
int L = 0;
while( j >= 0 && arr[j] == arr[m] ){
L++;
j--;
}
if( j > 0 && L > 0 )
*first=j+1;
else if( j==0 && L==0)
*first=m;
else if( j > 0 && L==0 )
*first=m;
else if(j < 0 && L==0 )
*first=m;
else if( j < 0 && L > 0 )
*first=0;
else if( j=0 && L > 0 )
*first=j+1;
int h = m + 1;
int R = 0;
while( arr[h]==arr[m] && h <= w ){
R++;
h++;
}
*count = (R + L + 1);
return *first;
}
else if( m==-1)
return -1;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.