Given an array containing the sequence 1,5,29,45,67,76,92,104,187,234 (in that o
ID: 3895412 • Letter: G
Question
Given an array containing the sequence 1,5,29,45,67,76,92,104,187,234 (in that order)
1. state each comparison made in finding the number 234 using linearsearch. (For example, 234:1 is a comparison of 234 with1.)
234:1, 234:5, 234:29, 234:45, 234:67, 234:76, 234:92, 234:104, 234:187,
234:234
2. state each comparison made in determining that the number 48 is not present using linear search.
48:1, 48:5, 48:29, 48:45, 48:67, 48:76, 48:92, 48:104, 48:187, 48:234
3. Given an array containing the sequence 1,5,29,45,67,76,92,104,187,234 (in that order)
1. state each comparison made in finding the number 234 using binary search. (For example, 234:1 is a comparison of 234 with1.)
234:67, 234:104, 234:234
2. state each comparison made in determining that the number 48 is not present using binary search.
234:67, 234:29, 234:45
Explanation / Answer
Given array sequence 1,5,29,45,67,76,92,104,187,234
1.In linear search,the required element to be searched is compared with each element in array in the same order in which it is available in array.
1.1).here ,234 need to be find .so,we start with first element 1,then 5,then 29...until either array is over or element is found.
required comparisons:-
234:1
234:5
234:29
234:45
234:67
234:76
234:92
234:104
234:187
234:234 successful
1.2).Here,48 needs to be find.so,we follow the same procedure as above.we compare it with each element until 48 is found or array is over.
48:1
48:5
48:29
48:45
48:67
48:76
48:92
48:104
48:187
48:234 unsuccessful search
3). array given = 1,5,29,45,67,76,92,104,187,234
3.1). here ,to find we have to apply binary search.
in binary search we,have to follow these algorithms:-
BS(a,i,j,x)// a is array with starting index i ,ending index j and x is element to be searched
{
if(i==j)
{
if(a[i]==x)
return i;
else
return -1;// -1 indicates unsuccessful searching
}
else
{
m = floor((i+j)/2);
if(a[m] == x)
return m;
else
{
if(a[m] > x)
BS(a,i,m-1,x)// if smaller go left
else
BS(a,m+1,j,x)// if greater go right
}
}
according to above algorithm,required comparions
234:67
234:104
234:234
3.2).here,48 is to be found
following the same procedure as above,we get
required comparisons are:-
48:67
48:5
48:29 here,-1 is returned means unsuccessful searching
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.