Write the fill Random, linearSearch, and binarySearch functions in the standard

Question

Write the fill Random, linearSearch, and binarySearch functions in the standard way. The following code fragment illustrates how they are used: const int SIZE = 1234567; /* size of the array */int a[SIZE]; /* declare the array  */fill Random (a, SIZE, 100, 200); /* fill with random integers */int loc444LS -linearSearch(a, SIZE, 444);  /* get index of ele = 444 */sort(a, SIZE);/* don't worry about this */int loc444BS - binarySearch(a, SIZE,    444);/* get index of ele = 444 */. Finish this function. It fills the array with integers from f irst to last, both ends included. void fillRandom(int x[], int size, int first, int last){

Explanation / Answer

void fillRandom (int x[], int SIZE, int first, int last)
{
int i;
for (i = 0; i < SIZE; ++i)
{
x[i] = ( rand() % first ) + last;
}

}

void swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}

// A function to implement bubble sort
void sort(int A[], int SIZE)
{

int i, j;
for (i = 0; i < SIZE-1; i++)   
{
for (j = 0; j < SIZE-i-1; j++)

{
printf("kakajaj ");
if (A[j] > A[j+1])
swap(&A[j], &A[j+1]);
}
}
}

// Invariant: A[l] <= key and A[r] > key
// Boundary: |r - l| = 1
// Input: A[l .... r-1]
int binarySearch(int A[], int SIZE, int key)
{
int m;
int l = 0;
int r = SIZE -1;
while( r - l > 1 )
{
m = l + (r-l)/2;

if( A[m] <= key )
l = m;
else
r = m;
}

if( A[l] == key )
return l;
else
return -1;
}

int linearSearch(int A[], int SIZE, int key)
{
int i;
for (i = 0; i < SIZE; ++i)
{
if(A[i] == key) return i;
}

return -1;
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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