Write a function that accepts random numbers as input. Implement binary search t

Question

Write a function that accepts random numbers as input. Implement binary search to find a particular number in the list. The function should return the position of the number in the array or -1 if the number is not found. (most of this is already implemented in Chapter 8). Does the function always find the number you ask for? Implement a function that implements linear search. Does linear search find the answer always?

Next write a function that sorts the array (use selection sort). Sort the list using this function. Then try binary search again, does it find the number if it exists in the list? Try linear search. Run the program for different values that are in the list. Each time count how many times the loop is executed in binary search? in linear search? Which search is faster?.

Explanation / Answer

1)#include <stdio.h>

int main()
{
int i, element1, elementlast, middle, n, search, array[100];

printf("Enter number of elements ");
scanf("%d",&n);

printf("Enter %d integers ", n);

for (i = 0; i < n; i++)
scanf("%d",&array[i]);

printf("Enter value to find ");
scanf("%d", &search);

element1 = 0;
elementlast = n - 1;
middle = (element1+elementlast)/2;

while (element1 <= elementlast) {
if (array[middle] < search)
element1 = middle + 1;
else if (array[middle] == search) {
printf("%d found at location %d. ", search, middle+1);
break;
}
else
elementlast = middle - 1;

middle = (element1 + elementlast)/2;
}
if (element1 > elementlast)
printf("Not found! %d is not present in the list. ", search);

return 0;   
}

2)

#include <stdio.h>

int main()
{
int array[100], n, i, d, position, swap, element1, lastelement, middle, search ;

printf("Enter number of elements ");
scanf("%d", &n);

printf("Enter %d integers ", n);

for ( i = 0 ;i < n ; i++ )
scanf("%d", &array[i]);

for ( i = 0 ; i < ( n - 1 ) ; i++ )
{
position = i;

for ( d = i + 1 ; d < n ; d++ )
{
if ( array[position] > array[d] )
position = d;
}
if ( position != i )
{
swap = array[i];
array[i] = array[position];
array[position] = swap;
}
}

printf("Sorted list in ascending order: ");

for (i = 0 ; i < n ; i++ )
printf("%d ", array[i]);

printf("Enter value to find ");
scanf("%d", &search);

element1 = 0;
lastelement = n - 1;
middle = (element1+lastelement)/2;

while (element1 <= lastelement) {
if (array[middle] < search)
element1 = middle + 1;
else if (array[middle] == search) {
printf("%d found at location %d. ", search, middle+1);
break;
}
else
lastelement = middle - 1;

middle = (element1+lastelement)/2;
}
if (element1 > lastelement)
printf("Not found! %d is not present in the list. ", search);

return 0;   
}

the complexity of binary search is better .

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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