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

Expected number of comparisons
$= 1 \times$ Probability of first element being $x + 2 \times$ Probability of second element being $x + \ldots  +n  \times$ Probability of last element being $x$.

$= \frac{1}{n} + \frac{2}{n} + \frac{3}{n} +\ldots +\frac{n}{n} $

$ = \frac{\left ( \frac{n\times (n+1)}{2} \right ) } {n} $

$ = \frac{n+1}{2}$

Correct Answer: $C$

Comments

MAM :)
FOR PROBABILITY PART YOU ARE NOT CONSIDERING CONDITIONAL PROBABILITY AS PROBABILITY OF CURRENT FAILURE OR SUCCESS IS DEPENDENT ON PREVIOUS PROBABILITY OF FAILURE.

I HAVE EXPLAINED IN MY ANSWER.

---

@Arjun  why this is wrong

Expected number of comparisons

=1×Probability of first element be x + 2×Probability of second element be x + .... +n × Probability of last element be x.

=1×1/n+2×(1-1/n)×(1/(n-1))+.....+n×(1-1/n)×(1-1/(n-1))×....×(1/2)×1

=1×1/n+2×((n-1)/n)×(1/(n-1))+..+n×((n-1)/n)×((n-2)/(n-1))×..×(1/2)×1

=1/n+2/n+3/n+......+n/n

=(1/n)×(1+2+3+.......+n)

=(1/n)×∑(n)

=(1/n)×(n×(n+1))/2

=(n×(n+1))/(n×2)

=(n+1)/2 ,

---

@Arjun  

why

​​​​@Mithlesh Upadhyay's comment is wrong??

Answer 2

First consider smaller example...
say list given  = {3,1,2} and say you want to search element '2' in sequential way.So first you will visit first element and compare it with '2' .If it is '2' then your search will end at first element with only 1 comparison. But if it is not equal to '2',then you compare it with second element. so second element is '1' so again search was unsuccessful and comparison required was total '2' i.e. b/w '2' & '3' and b/w '2' & '1' and so on.
So if required element is found at first position , no of comparison = 1;
if required element is found at second position , no of comparison = 2 ...and so on.

Now since our list is not sorted so it can be anything e.g. list can be {1,2,3} or {3,2,1} or {2,3,1}etc.So the element we are looking for may be  present at any of these three positions with equal chances of 1/3.

Now consider our list containing 'n' elements. So element to be searched can be present at any of these 'n' positions in the list with equal chance(probability) of 1/n.

Total comparison required = No.of comparison if element present in 1st position + No.of comparison if element present in 2nd position + .......+ No.of comparison if element present in nth position
= 1 + 2 + 3+ ......+n = n(n+1)/2
Since there are 'n' elements in the list.
So avg. no. of comparison =  Total comparison/total no of elements   = [n(n+1)/2] / n   = (n+1)/2.

Comments

Should be added as best answer :)

---

very good explanation, thank u.

---

clear concept..thanks

Answer 3

Searching an element in an array, the search starts from the first element till the last element.
The average number of comparisons in a sequential search is (N+1)/2 where N is the size of the array. If the element is in the 1st position, the number of comparisons will be 1 and if the element is in the last position, the number of comparisons will be N.

Answer 4

For our array, the element to be searched sequentially gives the following possibilities:

If our element is present in the $1^{st}$ index itself: Total no. of comparisons=1

If our element is present in the $2^{nd}$ index of array: Total no. of comparisons=2

If our element is present in the $3^{rd}$ index of array: Total no. of comparisons=3

.

.

.

If our element is present in the $n^{th}$ index of array: Total no. of comparisons=n

Average number of comparisons=$\frac{1+2+3+.....n}{n} =\frac{n(n+1)}{2*n}=\frac{n+1}{2}$