GATE CSE 1996 | Question: 2.13, ISRO2016-28

Question

The average number of key comparisons required for a successful search for sequential search on $n$ items is

• A. $\frac{n}{2}$
• B. $\frac{n-1}{2}$
• C. $\frac{n+1}{2}$
• D. None of the above

Comments

please explain me

---

in this question ask an average number of key comparison so why calculating Expected number of comparisons 

@Bikram

@Arjun 

 

---

NUMBERPHILE LOVES AND COMPUTERPHILE LOVERS HIT LIKE MAN

Answer 1

MOST OF THE STUDENTS ARE CONFUSED ABOUT RESPECTIVE PROBABILITIES FOR EACH RANDOM VARIABLE.

HERE I HAVE TRIED TO EXPLAIN HOW WE CAME TO “I/n” PROBABILITY FOR EACH RANDOM VARIABLE.

NOTE: USE CONDITIONAL PROBABILITY.

😎

Answer 2

sequential search can be applied on both sorted and unsorted array.

for(i=0;i<n;i++)

{{ if (a[i]==target)

return i;}

return -1;

}

suppose array is 9 6 5 0 8 2

best case if we have to search 9.  comparsion =1

worst case if we have to search 2   comparison =6

average=(6+1)/2

so for n the key comparison will be (n+1)/2

Answer 3

I do this question in another way

Supposed we have n  elements  in  an array
 
Now the qn is asked for success ful search ,ok

Now suppose our key elements is store at index 0 then the number of search is 1

And again supposed our key elements is store at index 1 then number of successful search is 2

And again supposed our key elements is store at index 2then number of successful search is 3

Now suppose if our element is store at last position then our number of successful search is n


Now examine fully
The total number of success full search(for all elements stored in an array) is:
1+2+3+4+.......n


That the summation comes to [n(n+1)]/2
According to summation of n natural number




Ok

But in the qn it is asked about average
So we need to divide it by n

So[ n(n+1)/2]/2

That's equal to ( n+1)/2



I think u got it way   


Reply me that my answer(way) is correct  or not

Comments

Your answer is correct and in fact same as the selected answer as we assume same probably for every position for the successful search.

Answer 4

ans is D

Comments

provide explanation

---

Since it is a linear search we can find the element in any of the k position for a successful search.  Therefore the average number of search is

i=n

( ∑k)/n = n(n+1)/2n = (n+1)/2

i=1

---

Can you please explain ur logic .

---

https://gateoverflow.in/840/gate2002-2-10