Objectives: Working with arrays and functions
Pre-requisite(s): Read and review chapters 1-6.
Write a C program that creates an array of 500 integer elements and loads it with each value equal to the subscript’s square, and then write a sequential and a binary search algorithm to see whether a number is a perfect square. Use a loop to load the array. Prompt the user for a positive integer value less than 250,000. Test the functions by calling them from a simple interactive main() function using a menu, with different values used to select the choice of function. Overall, you should have one C program (call it firstnameLastname_Lab2.c) containing one main() function and at least the following functions:
Pre-requisite(s): Read and review chapters 1-6.
Write a C program that creates an array of 500 integer elements and loads it with each value equal to the subscript’s square, and then write a sequential and a binary search algorithm to see whether a number is a perfect square. Use a loop to load the array. Prompt the user for a positive integer value less than 250,000. Test the functions by calling them from a simple interactive main() function using a menu, with different values used to select the choice of function. Overall, you should have one C program (call it firstnameLastname_Lab2.c) containing one main() function and at least the following functions:
-
1- void loadArray(int nums[], int size): To load the array nums with its
subscript’s squares (eg. {0,1,4,9,16,25,...})
-
2- int binarySearch(int nums[], int size, int key): To search the
input array for a key using binary search approach and return the number of
comparisons.
-
3- int sequentialSearch(int nums[], int size, int key): To search
the input array for a key using sequential search approach and return the number
of comparisons.
-
4- int getKey(): to get a valid integer key (between 0 and 250,000) from the user
to search.
#include<stdio.h>
void loadArray(int nums[], int size)
{
int i;
for(i=1; i<=size; i++)
nums[i-1] = i*i;
}
int binarySearch(int nums[], int size, int key)
{
int comparisions = 0;
int left = 1, right = size-1;
while(left<=right)
{
int middle = left + (right-left)/2;
comparisions++;
if (nums[middle] == key)
{
printf("%d is a perfect square\n", key);
return comparisions;
}
comparisions++;
if (nums [middle] < key)
left = middle + 1;
else
right = middle - 1;
}
printf("%d is not a perfect square\n", key);
return comparisions;
}
int sequentialSearch(int nums[], int size, int key)
{
int i, comparisions = 0;
for(i=0; i<size; i++)
{
comparisions++;
if(nums[i] == key)
{
printf("%d is a perfect square\n", key);
return comparisions;
}
}
printf("%d is not a perfect square\n", key);
return comparisions;
}
int getKey()
{
int key;
while(1)
{
printf("Enter key(1-250000): ");
scanf("%d", &key);
if(key<1||key>250000)
printf("Invalid key.\n\n");
else
break;
}
return key;
}
int main()
{
//variables
int nums[500], size = 500;
loadArray(nums, size);
int choice, key;
//loop for menu
while(1)
{
//choice
printf("Menu\n1.Binary Search\n2.Sequencial Search\n3.Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
//if 3, break
if(choice == 3)
break;
//otherwise perform action accordingly
switch(choice)
{
case 1:
key = getKey();
printf("Comparisions: %d\n\n", binarySearch(nums, size, key));
break;
case 2:
key = getKey();
printf("Comparisions: %d\n\n", sequentialSearch(nums, size, key));
break;
default:
printf("Invalid choice.\n\n");
break;
}
}
return 0;
}
Comments
Post a Comment