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.
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