unit 2 First.pptx Searching - Linear and Binary Search

unit 2 First.pptx Searching - Linear and Binary Search

1. SANJIVANI K. B. P. POLYTECHNIC, KOPARGAON With NBA ACCREDIATED programs , Approved by AICTE, New Delhi, Recognized by Govt. of Maharashtra , Affiliated to Maharashtra State Board of Technical Education, Mumbai, ISO 9001:2015 Certified Institute Department:- Computer Technology Class:- CM3I Name of Subject:- Data Structures Using 'C‘ MSBTE Subject Code:- 22317 Name of Faculty: Prof. Vaibhav A. Parjane 1

2. UNIT 2 Searching and Sorting

3. Unit Outcome After going through this unit, the student will be able to : 2a. Explain working of the given search method with an example. 2b. Write an algorithm to search the given key using binary Search method 2c. Write an Algorithm to sort data using a specified sorting method. 2d. Explain the working of given sorting method step­ by-step with an example and small data set.

4. Topic to be Covered Searching Linear Search 4 Sanjivani K. B. P. Polytechnic, Kopargaon Department of Computer Technology Prof. Vaibhav A. Parjane

5. Searching 1. Searching is the process to find the given element in the list with its position. 2 . The search is said to be successful if the given element is found i.e. the element does exist in the collection such as an array; other wise it is unsuccessful.

6. Introduction: ( Searching) Searching: Searching is a process of finding the location of a particular element in an array is called searching. There are two types of searching: Linear Search: Binary Search:

7. Linear Search Linear search or sequential search is a method for finding a particular value in a list that consists of checking every one of its elements One element at a time and in sequence, until the desired one is found. In Linear Search we start searching – sequentially starting from the first element and continue until we find the target [ element ] or we are sure that it is not in the list . It is simplest search algorithm

8. Linear Search Consider an array of 20 elements . Suppose, element 8 is to be search in the array.

9. Linear Search Algorithm Read the total number of array elements in ‘n’, Set flag = o. Read the ‘n’ array elements in array ‘a’ as – a [o] … a [n]. Read the target to be searched in variable ‘Key’. For i = o to n. Compare each element of array with ‘Key’ => If (a [ i ] = = Key ) If true then set flag = 1, and close the loop. 5. Now, if ( flag = = 1) means target found, so print the location at which target is found. 6. Stop

10. Program:- # include < stdio.h > int main () { int a[20], n,i , key , pos , flag = o; clrscr (); printf (“\n Enter the number of elements in array : \n”); scanf (“% d”, &n); printf (“\n Enter Array element = “); For ( i = o; i < n; i + +) { scanf (“%d”, &a[ i ]); } printf (“\n Enter the number to search “); scanf (“%d”, &key );

11. Program :- .. continued For ( i =o; i <n; i + +) { if (a[ i ] == k ey ) { pos = i ‘; flag = 1; break ; } } if (flag == 1 ) printf (“\n Element located as %d “\n”, pos ); else printf “\n Element not present “); getch (); }

12. Linear Search The complexity of any searching algorithm depends on number of comparisons required to find the element Performance of searching algorithm can be found by counting the number of comparisons in order to find the given element.

13. Advantages Simple and easy method. Efficient for only small lists. Better for unsorted data .

14. Disadvantage Highly inefficient for large data.