Linear Search Data Structure

Linear Search algorithem.

1. Presentation on Linear search Data Structure

2. Group Members MCS-13-08 Muhammed Talha MCS-13-03 Arslan Azam MCS-13-38 Aitazaz Ahsan MCS-13-39 Tayyaba Ghani MCS-13-22 Abida Bibi

3. Contents Introduction to Search What is Linear Search ? Example of Linear Search ? Pseudo code C++ Code linked list code of Linear Search Worst Case Best Case Discussion

4. Muhammed Talha Search & Linear Search

5. What is Search ? The  definition  of a  search  is the process of looking for something or someone Example : An example of a  search  is a quest to find a missing person

6. Linear Search : Algorithm involves checking all the elements of the array(or any other structure) one by one and in sequence until the desired result is found.

7. Linear Search Example If you are asked to find the name of the person having phone number say “1234” with the help of a telephone directory . Since telephone directory is sorted by name not by numbers,we have to go through each and every number of the directory

8. Pseudocode For all elements Check if it is equal to element being searched for. If it is ,return its position. else continue.

9. Arslan Azam Linear Search Example by C++ Program

10. C++ code void iterSearch (const double data [ ], int n,double key) //const for safety ,we want to keep array unchanged { for( int i =0;i<=n-1;i++) //looping through all elements of the array { if(data[ i ]==key) { cout <<key<<" found at index "<< i <<" of the array"<< endl ; break; //if element is found,come out of the loop } if( i ==n-1) //searched through the array,still not found cout <<"\n Element not found \n"; } }

11. Atizaz Ahsan Linear Search Example by using Linked List

12. Linear Search using Linked List void List::find() { int n, count = 0; cout <<"Enter data to find in the list : "; cin >>n; Node * tmp = head; while ( tmp != NULL ) { count = count + 1; if( n == tmp ->Data()) { cout <<"The data found on node number "<< count << endl ; break; } tmp = tmp ->Next(); } }

13. Abida Bibi Advantages of Linear Search

14. Advantages of Linear search If the first number in the directory is the number you were searching for ,then lucky you!!. ●Since you have found it on the very first page,now its not important for you that how many pages are there in the directory. ●Whether if it is of 1000 pages or 2000 pages it will take u same time to find you the number ,if it is at the very beginning . ●So it does not depends on no. on elements in the directory.Hence constant time .

15. Tayyaba Ghani Disadvantages of Linear Search

16. Disadvantages of Linear search It may happen that the number you are searching for is the last number of directory or if it is not in the directory at all. In that case you have to search the whole directory. Now number of elements will matter to you.if there are 500 pages ,you have to search 500;if it has 1000 you have to search 1000. Your search time is proportional to number of elements in the directory. No of elements No of comparisons to be done 15 15 600 600

17. Discussion 1.Sorted array is not needed. 2.Works fine for small number of elements .Search time increases with number of elements. 3.Elements with higher probability of being searched should be kept in the beginning.

18. Question ?

19. Thank You 