Saturday, 22 October 2016

Linear Search - Is it a joke?

Whats Up? How are you people? You must be thinking that I am off my head. But luckily this time I'm in my senses. Yes! you got the post title correct, Linear Search, I will talk about it and Wait! Wait!Wait! I know you're mind must be brimming up with thoughts like Linear Search? Really?
F...k off ! Everybody knows it.  But I will tell you a interesting thing which I guess you might not have noticed before. So stay Tuned.

First comes the code in C++ then the talk- which the crux of this post.

#include<iostream>
#include<vector>
using namespace std;

int main(){
    int value;
    cout<<"Enter the value to be searched"<<endl;
    cin>>value;
    vector<int>v = {8,3,5,1,0,9,23,43,6,4};
    for(auto i = 0;i!=v.size();++i){
        if (value == v[i])
            cout<<"Value Found";}
    return 0;
}
If you're smart then tell what me what is the average number of comparisons made before you find the value?

Answer: Lets get started! The value is equally likely to be in any of the positions. So if the value is in the fist position:1 comparisons , If the value is in the 2nd position:2 comparisons, Similarly, if the value is in the ith position: i comparisons.

So the average of all these possibilities = (1/n+2/n+3/n+.......+n-1/n+n/n)
Taking n common from denominator,       (1+2+3+.......+n-1+n)/n
The sum of first n terms is equal to,           [n(n+1)/2]/n

Which Gives us the final answer =  (n+1)/2

So the average number of comparisons before we find the value is  (n+1)/2    comparisons.

If you knew it already Please forgive me. I won't dishearten you from next time.

No comments:

Post a Comment