Linear Searching

In our daily life we often search thing like books, movie etc. Similarly in computer science searching is an important area. There are several search techniques some are easy to understand today I will discuss an easy search technique called linear search which complexity is O (n).

Suppose we have an array of String which contains name of 5 chocolates now we want to do some search.

img

So in linear search we start form the first or last and do a check that the current element is our searched item or not, if we found it then return true or else move to next element until we have searched the whole array. That’s why the complexity is O (n) because in worst case the searched item can be in the last position of the array or can be not present.

Case 1: Search a. Found it; a is in the index 0 position.
Case 2: Search g. Not found it. (Worst case)
Case 3: Search e. found it; e is in the index 4 position. (Worst case)

But in real life the input data is not too small always. For 1000000 data linear search will be too slow, yes there are other search techniques which are faster than linear search.

S. Mahbub – Uz – Zaman
Monday, September 26, 2011

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s