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