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. $\dfrac{n}{2}$
• B. $\dfrac{n-1}{2}$
• C. $\dfrac{n+1}{2}$
• D. None of the above

Comments

@Shaik Masthan sir excellent expalanation. now got it. 

Thanks a lot 

---

Correct me if i am wrong !
best case when the element we want to find is the first element , no. of comparison = 1
worst case when the element we want to find is the last elemnt , no. of comparisons = n
avg case =(n + 1)/2 isn't ?

---

if we check comparisons per pass thati is
for pass1 = (n - 1) comparisonss, pass2 = (n - 2) comparison, ..... for pass(n-1) = 1 comparison

hence 1 + 2 + 3 + .... + (n - 1) = n (n - 1) / 2
so C option also correct

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

@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??

---

@Puja Mishra
The formula (BC + WC) / 2 is NOT a general way to find the average case.
It's coincidentally correct here but we can't generalize
And in this context @Arjun sir is correct
the average number of comparisons is the expected number of comparisons for a successful search.

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 $\text{'2' & '3' }$ and b/w $\text{'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 comparisons required $= $ No.of comparison if element present in $1^{st}$ position $+$ No.of comparison if element present in $2^{nd}$ position $+$ $.......+$ No.of comparison if element present in $n^{th}$ position.

$= 1 + 2 + 3+ ......+n = n(n+1)/2$
Since there are $'n'$ elements in the list.

So avg. no. of comparison $=$  $\frac{\text{Total comparison}}{\text{total no of elements}} $  = $\frac{\frac{n*(n+1)}{2}} { n} $  $=$ $\frac{(n+1)}{2}$.

Comments

clear concept..thanks

---

superb explaination 👏

---

Crystal clear

Answer 3

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}$

Answer 4

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 5

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.

😎

Comments

@Jyotish Ranjan can u please explain how u are wrting the probabilities of  2, 3 .. 

---

Note that it is like : index are not repeated nature.

Probability for first index contain our required value =$\frac{1}{n}$

Probability for second index contain our required value = $\frac{n-1}{n}. \frac{1}{n-1}= \text{unsucessful at first index x successful at second index}$

Answer 6

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