SR.
NO NAME OF STUDENTS PERCENTAGE
1 SHIFA TAMBOLI 92.50%
2 SANIYA DEVALE 92.38%
3 SUMAIDA RAMPURE 92.13%
4 MEHER MULANI 91.63%
5 TANMAY GORAD 90.38%
• UNIT- I – Introduction to Data Structures
• UNIT-II – Searching and Sorting
• UNIT-III – Stacks and Queues
• UNIT-IV – Linked List
• UNIT V – Trees and Graphs
UNIT – II
• Searching and sorting
• Searching : 1) Linear Search 2)Binary Search
• Sorting : 1) Bubble Sort 2) Selection Sort
3) Insertion Sort 4) Radix Sort
• Searching
What is searching ? State two methods of
searching?
(W-9,11,12,13,15,16)
• Searching is a technique of finding an element in a
given list of elements.
• List of elements could be represented using Array,
linked list and Tree.
• Search a list of records to identify a particular
record.
• Each record is uniquely identified by its key field
and searching is carried out on the basis of key
field.
• If search results in locating the desired record then
the search is said to be successful.
• Otherwise the search operation is said to be
unsuccessful.
• 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
• Best Case : the element is found during the first
comparison itself.
• Worst Case : The element is found only in last
comparison.
• Average Case : Number of comparisons should be
more than comparisons in the best case and less
than the worst case.
1.Sequential / Linear Search
2.Binary Search
• Searching
• Explain Linear search with example.
Explain the linear search algorithm. Also
give its limitation ?
(W-9,10,12,17
S-9,10,13,15)
• Elements are checked sequentially starting from first node to the
last node.
• The process of searching terminates when the list is exhausted or
a comparison results in success.
• Algorithm : Searching an element „Key‟ in the array „a[]‟ having n
elements .
Step 1: Start
Step 2: Repeat for i=0 to N-1
Step 3: If Array[i]== key
print index and return from loop
Step 4: If i==N
Print “Element not found”
Step : Stop
• The search algorithm starts comparison between the first element
of a[ ] and „key‟
• As long as a comparison does not result in success, the algorithm
proceeds to compare the next element of a[ ] with „key‟
• The process terminates when the list is exhausted or the element is
not found.
Int sequential (int a[ ] , int key , int n)
{
int i=0;
while(i<n)
{
if (a[ i ] == key)
return ( i ) ;
i++;
}
return (-1);
}
The function returns the index of the element in a[ ] foe successful search.
A value -1 is returned if the element is not found.
The time complexity of linear search is O(n).
At the most n comparison will be required to search a data element in an
array.
#include <stdio.h>
#include<conio.h>
int main()
{
int array[5], key, i, n;
printf("Enter number of elements in array\n");
scanf("%d", &n);
printf("Enter %d integer\n", n);
for (i= 0; i < n; i++)
scanf("%d", &array[i]);
printf("Enter a number to search\n");
scanf("%d", &key);
for (i = 0; i < n; i++)
{
if (array[i] == key) /* If required element is found */
{
printf("%d is present at location %d.\n", key, i+1);
break;
}
}
if (i == n)
{
printf("%d isn't present in the array.\n", key);
return 0;
}
}
• Its time complexity is O(n). It should not be
used for a long list.
• If the number of elements in array is very
high, this method is very inefficient and slow.
printf("Enter number of elements in array\n");
scanf("%d", &n);
printf("Enter %d integer(s)\n", n);
for (i= 0; i < n; i++)
{ 0 1 2 3 4
scanf("%d", &array[i]); 5 6 4 2 9
}
N =5
Initialization Condition Operation Increment/
&array[i] User Input Decrement
i=0 i<n i++
i=0 0<5 &array[0] 5 1
i=1 1<5 &array[1] 6 2
i=2 2<5 &array[2] 4 3
i=3 3<5 &array[3] 2 4
i=4 4<5 &array[4] 9 5
i=5 5<5 Condition False ,
Exit from for loop
printf ("Enter a number to search\n");
scanf ("%d", &key);
for (i = 0; i < n; i++)
{
if (array[i] == key)
{
printf ("%d is present at location %d.\n", key, i+1);
break;
}
}
n =5 , key =4
Initialization Condition Operation Increment/
array[i] == key result Decrement
i=0 i<n i++
i=0 0<5 array[0] == 4 5!=4 1
i=1 1<5 array[1] == 4 6!=4 2
i=2 2<5 array[2] == 4 4==4
Search successful , key is present at location i+1=2+1=3
0 1 2 3 4
5 6 4 2 9
if (i == n)
{
printf("%d isn't present in the array.\n", search);
return 0;
}
• Binary Search
• Explain Binary search algorithm, give
example to search an element using
binary search algorithm and also give its
advantage ?
(S-8,14
W-11,12,14,15,16,17)
• Linear search has a time complexity O(n) such
algorithms are not suitable for searching when
number of elements is very large.
• Linear search may need 1 million comparison for
searching an element in an array having 1 million
elements.
• Binary search exhibits much better timing behaviour
in case of large volume of data with timing
complexity O(log2 n)
• Binary search will require, just 20 comparisons for
the same task.
Number of comparisons for n= 220 (1million)
Binary search = log2 220 =20 comparisons
• Binary search uses divide and conquer approach to finds the
position of a specified value within a sorted array.
• Binary search is applicable only when the given array is
sorted in ascending order.
• Divide the list and locate the middle element of the list.
• It is then compared with the search element. If the search
element is less than the middle element, the first part of the
list is searched else the second part of the list is searched.
• The algorithm again reduce into two halves, locates the
middle element , and compare with search element.
• If the search element is less than the middle element , the
first part of the list is searched else the second part of the list
is searched.
• This process continues until the search element is equal to
the element or the list consists of only one element that is
not equal to the search element.
• Let a[Max] is array, n is the size of array and key is an
element to be searched.
1. Set i=0 (first element index), j=n-1 (Last element index) ,
C=(i + j)/2 (middle element index)
2. Repeat step 3 and 4 while i<=j and a[C]!=key
3. If key > a[C] then
set i=C+1
else
set j= C-1
4. Set C = (i + j)/2
5. If i <=j
then print “Index Position”
else print “Key not Found”
0 1 2 3 4 5
2 5 11 19 27 35
• a[6] is array, n=6 is the size of array and key=11 is an element to be
searched.
1. Set i=0 (first element index), j=5 (Last element index) ,
C=(i + j)/2 C=(0+5) /2 = 2.5 =2 (middle element index)
2. Repeat step 3 and 4 while i<=j and a[C]!=key If key > a[C] then
set i=C+1
else
set j= C-1
4. Set C = (i + j)/2
5. If i <=j
then print “Index Position”
else print “Key not Found”
• a[6] is array, n=6 is the size of array and key=11
i J=n-1 c= (i+j)/2
0 1 2 3 4 5
2 5 11 19 27 35 0 5 5/2=2.5=2
• Case 1: key==a[c] 11==11 condition is true
• Case 2: key>a[c]
• Case 3: key<a[c] c=2 index a[c] =11
while If else
i<=j a[C]!=key key > a[C] set i= C+1 set j= C- i j c= (i+j)/2
1
0<=5 11!=11
false
i <= j Return Return
c -1 i<=j && a[c]!=key
0<=5 2
0 1 2 3 4 5
2 5 11 19 27 35
• a[6] is array, n=6 is the size of array and key=2 is an
element to be searched.
1. Set i=0 (first element index), j=5 (Last element index) ,
C=(i + j)/2 C=(0+5) /2 = 2(middle element index)
2. Repeat step 3 and 4 while i<=j 0<=5 and a[C]!=key
a[2]!=2 11!=2
3. If key > a[C] then 2>11 ----false
set i=C+1
else if key==a[C] then
print “Key found”
else set j= C-1 j=2-1=1
4. Set C = (i + j)/2 c=(0+1)/2=0
i<=j 0<=1 a[2]!=2 2==2 Search terminates return(0)
• a[6] is array, n=6 is the size of array and key=2
• Case 1: key==a[c]
0 1 2 3 4 5 • Case 2: key>a[c]
2 5 11 19 27 35 • Case 3: key<a[c] 2<11 condition is true
i J=n-1 c= (i+j)/2
0 5 5/2=2.5=2
while If else
i<=j a[C]!=key key > a[C] set i= C+1 set j= C-1 i j c= (i+j)/2
0<=5 11!=2 2>11 false j = 2-1=1 0 1 0
0<=1 2!=2 false
0 1
2 5
i<=j Return Return
c -1
0<=1 0
• a[6] is array, n=6 is the size of array and key=41
0 1 2 3 4 5
2 5 11 19 27 35 • Case 1: key==a[c]
• Case 2: key>a[c] 41>11 condition is true
i J=n-1 c= (i+j)/2 • Case 3: key<a[c]
0 5 5/2=2.5=2
while If else
i<=j a[C]!=key key > a[C] set i= C+1 set j= C-1 i j c= (i+j)/2
0<=5 11!=41 41>11 i=2+1=3 3 5 4
3<=5 27!=41 41>27 i=4+1=5 5 5 5
5<=5 35!=41 41>35 i=5+1=6 6 5 5
6<=5
i<=j Return c Return -1
3 4 5 5
6>5 -1
19 27 35 35
• a[6] is array, n=6 is the size of array and key=17
0 1 2 3 4 5
2 5 11 19 27 35 • Case 1: key==a[c]
• Case 2: key>a[c] 17>11 condition is true
i J=n-1 c= (i+j)/2 • Case 3: key<a[c]
0 5 5/2=2.5=2
while If else
i<=j a[C]!=key key > a[C] set i= C+1 set j= C-1 i j c= (i+j)/2
0<=5 11!=17 17>11 i=2+1=3 3 5 4
3<=5 27!=17 17>27 false J=4-1=3 3 3 3
3<=3 19!=17 17>19 i=3+1=4 4 3 3
4<=3
i <= j Return c Return -1
4<=3 -1
3 4 5 3
19 27 35 19
int bin_search (int a[], int i, int j , int key)
{
int c;
c = (i + j)/2;
while(a[c]!key && i<=j)
{
if (key>a[c])
{
i=c+1;
}
else
{
j = c-1;
}
c=( i + j)/2;
}
if(i<=j)
{
return( c );
}
else
{
return(-1);
9,17,23,38,45,50,57,76,79,90
Search 10
Search 100
Search 38
11,5,21,3,29,17,2,43
Search 29
77,33,44,11,88,22,66,55
Search 88
• a[10] is array, n=10 is the size of array and key=10
0 1 2 3 4 5 6 7 8 9
9 17 23 38 45 50 57 76 79 90
c= (i+j)/2 • Case 1: key==a[c]
i J=n-1
• Case 2: key>a[c]
0 9 9/2=4.5=4 • Case 3: key<a[c] 10<45 condition is true
while If else
i<=j a[C]!=key key > a[C] set i= C+1 set j= C-1 i j c= (i+j)/2
0<=9 45!=10 10>45 J=4-1=3 0 3 C= 1.5 = 1
FALSE
• Case 1: key==a[c]
0 1 2 3
• Case 2: key>a[c]
9 17 23 38 • Case 3: key<a[c] 10<17 condition is true
while If else
i<=j a[C]!=key key > a[C] set i= C+1 set j= C-1 i j c= (i+j)/2
0<=3 17!=10 10>17 J=1-1=0 0 0 C= 0
FALSE
0
9
while If else
i<=j a[C]!=key key > a[C] set i= C+1 set j= C-1 i j c= (i+j)/2
0<=0 9!=10 10>9 0+1=1 1 0 0.5=0
0 1
9 17
while If else
i<=j a[C]!=key key > a[C] set i= C+1 set j= C-1 i j c= (i+j)/2
1<=0 9!=10
false
If else
i <= j Return c Return -1
1<=0 -1
5,9,11,15,25,29,30,35,40
Search 6
BFDACEIGHJ
Search H
23,12,5,29,10,65,55,70
Search 65
1.For(i=0;i<n;i++)
2.If ( condition )
{
………execute…………..
}
3. If (condition) 10th pass
{
……..execute……admiited
}
else
{
……………..execute…………not admitted
}
