Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

BCA – 402 DATA STRUCTURE and ALGORITHM

1. Introduction and Overview 1.2

Basic Terminology; Elementary data organization:- (a)
Data.
(b) Data item.
i) Group item.
ii) Elementary data item.
(c) Organization of data. i)
Attribute ii) Entity iii)
Entity set.
(d) Information. i) Field ii)
Record iii) File
(e) Primary key.
(f) Classification of record. i)
Variable length ii) Fixed
length.

(a) Data :- Data are simply value or set of value.

Ex.: “LATUR”, 8.
(b) Data item :- Data item is single unit of values.
Ex.: “LTUR”,67.
Further data item are get divided into two parts.
i) Group items ii) Elementary items.
i) Group items :- Data items that are divided into subitems are
called group items.
Ex.: Employee Name : More Ram Hari

By: Chimle Mahesh 1 / 35

Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

Employee name get divided into three subitems as first name, middle
name and last name.
ii) Elementary items :- Data items that are not divided into
subitems are called elementary item.
Ex.: 14 – 03 – 2022.
Social security number is treated as a single item.
(c) Organization of data :-
Collection of data are frequently organized into hierarchy of fields,
records and files.
- The above concept can be more cleared using following additional
terminology i.e. attribute, entity and entity set.
i) Attribute :- A attribute is a specified memory area used to store
data.
ii) Entity :- A entity is something that has retain attributes or
properties which may be assigned values. Here assigned values may
be either numeric or non-numeric.
Ex.: Attributes: Roll No. Name Grade
Values: 01 Ajay A
iii) Entity Set :- Entities with similar attributes form an entity set.
Each attribute of an entity set as a range of values, the set of all possible
values that could be assigned to the particular attribute.
Ex.: All the employees in an organization.
(d) Information :- A meaningful or processed data at particular attribute
is called as “information”.
The way that data are organized into the hierarchy of fields, records and files,
shows the relationship between attributes, entities and entity set as:
i) Field :- A field is a single elementary unit of information
representing an attribute of an entity.

1. By:Chimle Mahesh 2 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

ii) Record :- A record is the collection of field values of a given

entity. iii) File :- A file is the collection of records of the entities in a
given entity set.
(e) Primary key :- Every record in a file may contain many field items, but
the value in certain field may determine the record in the file uniquely. Such
a field K is called a primary key, and the values K1, K2, K3, …. Kn in such a field
are called key values or keys.
(f) Classification of Records :-
Records may also be classified according to the length.
A file can have fixed-length records or variable-length record. -
In fixed-length records, all the records contain the same data items
with the same amount of space assigned to each data item.
-In variable length records, file records may contain different lengths.
Ex.: Student records usually have variable lengths, since different student
take different number of courses.
Usually variable length records have a minimum and a maximum
length.

1.3 Data Structures :-

The logical or mathematical model of a particular organization
of a data is called a data structure.
The choice of a particular data model depends on two considerations:
i.The data model must be large in structure to show the actual
relationship of the data in the real world. ii.The structure should be
simple enough that one can effectively process the data when necessary.

By:Chimle Mahesh 3 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

Following figure shows types of data structures:

Data Structure

[A] Primitive [B] Non-Primitive

Int
Float i) Linear ii) Non-linear
Character Arrays Tree
Boolean Stack Graph
Queue

Linked list
[A] Primitive Data Structure :-
Primitive data structure are basic data types i.e. int, real, character,
Boolean, float. These data types are primitive because they are directly
understand by the machine.

[B] Non-Primitive Data Structure :-

Linear and non-linear data structures are non-primitive data
structures.
❖ Linear Data structure :- Linear data structure’s are,
a) Arrays.
b) Stack.
c) Queue.
d) Linked list.
I) Arrays: -
The simplest type of data structure is linear array.

1. By:Chimle Mahesh 4 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

Using a linear array, a list of finite number ‘n’ of similar data elements
referenced respectively by the set of ‘n’ consecutive (serially)
numbers, usually 1, 2, 3, ……….. n.
The elements of an array A may be denoted by the notation :
1. Subscript notation as A1, A2, A3, ……, An.
2. Parenthesis notation as A(1), A(2), A(3), …….., A(n).
3. By the bracket notation as A[1], A[2], A[3], ……., A[n]
Regardless of the notation, the number K in A[K] is called a
subscript and A[K]is called a subscripted variable.
II) Stacks :-
A stack, also called a last-in-first-out (LIFO) system, is a linear list in
which insertions and deletions place only at one end, called the Top.
This structure is similar in its operation to a stack of dishes on a spring
system as shown in following figure.
TOP

Disk

Sprig Container

As container is open at top side, new dishes are interested only at the
top of the stack and dishes can be deleted only from the top of the
stack.
III) Queue :-
A queue, also called a first-in first-out (FIFO) system, is a linear list in
which deletions can take place only at one end of the list, the ‘front’ of

By:Chimle Mahesh 5 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

the list, and insertions can take place only at other end of the list, the
‘rear’ of the list.
The structure operates in a same way as line of people waiting for bus
at bus-stop as Bus Stop shown in
figure.

Front -End

Rear-End
Fig: Queue of People

IV) Linked List :-

- A linked list, or one way list is a linear collection of data
elements, called ‘nodes’.
- Where the linear order is obtained by using pointers.
- Every node of linked list is get divided into two fields:
1. The first field is INFO which is used to store information of
the element.
2. The second field is LINK or next pointer field which is used to
store address of the next node in the list.
- Following figure shows a linked list with four nodes.

START

Next pointer field of second node.

Information field of second node.

Fig. Linked List with 4 nodes.

1. By:Chimle Mahesh 6 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

- It is clear that, in above fig. each node is pictured with two fields.
- The left field use the actual information, and right field use store
the address of the next node.
- Arrow shows the order of the nodes.
- The next pointer or LINK field of the last node contains a invalid
address called ‘null pointer’.
- The null pointer (X) is used to shows the end of the list.
- The linked list has also a list pointer variable called START which
contains address of first node in the list.
- The starting address o the list which is stored in START is used
to traverse the whole linked list.
- Here if the linked list has no any node then such a list is called
‘null list’ or ‘empty list’ and it is denoted by the null pointer
assigning to START i.e. START = NULL.
❖ Non – Linear Data Structure :-
Tree and graph are the non – linear data structure.
a) Tree :- data frequently contain a hierarchy relationship between
various elements, the data structure which shows such relationship is
called ‘Tree’.
Getting more about trees consider the following two examples.
i) Record structure. ii) Algebraic
expression.
i) Record Structure :- An employee personal record may contain
following data items.
Ex.: Social_security_no Name Address Age Salary.

By:Chimle Mahesh 7 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

- In above data items, name and address may be group items with
sub item i.e.
Name :- F_Name, M_Name, L_Name.
Address :- Street Address & Area Address.
- Further are its may be group item having sub item city, state and
pin code number.
- The hierarchical structure of above data element is in term of
tree’s is as follows,

Employee

Social Security No Name Address Age Salary

F_Name Street

M_Name Area

L_Name

City

State

Pin Code

This tree structure in terms of level numbers is pictured as bellow,

01. Employee
(2) Social Security Number
(2) Name

1. By:Chimle Mahesh 8 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

(3) F_Name
(3) M_Name
(3) L_Name
(2) Address
(3) Street
(3) Area
(4) City
(4) State
(4) Pin Code
(2) Age
(2) Salary.

ii) Algebraic Expression :- Consider the algebraic expression (5x

– y)3 * (a + 10b). Using vertical arrow for expatiation and asterisk (*)
for multiplication even algebraic expression can be represented
interims of trees as follows,

b) Graph :- Data sometimes contain a relationship between pairs of

elements which is not necessary hierarchical in nature. The data
structure which shows such type of relationship is called a ‘Graph’. Ex.:
Consider an airline flies only between the cities that are connected by
lines as shown in following fig.

By:Chimle Mahesh 9 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

Delhi

Mumbai Kolkatta

Aurangabad Pune

Fig. A graph shows airlines flies between cities .

1.4 Data Structure Operation :-

- A data structure that one choose for a given situation depends
on a frequency with which specific operations used to process
data.
- There are nearly eight operation in data structure.
- Out of them first four play major role. They are as follow,
1. Traversing.
2. Searching.
3. Inserting.
4. Deleting.
5. Sorting.
6. Messaging.

1. By:Chimle Mahesh 10 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

7. Copying.
8. Concatenation.
1. Traversing :-
- This operations is used to accessing each record exactly once of
process certain items in the records.
- Ex.: We have 1, 5, 10, 7 items into data structure.
- Then access (visit) all items means read one five, seven, ten in
certain manner called as ‘Traversing’.
2. Searching :-
- This operation is used to finding the location of the record with
the given key value.
- Ex.: If we have data 1, 5, 10, 7 stored sequentially.
- We want to find location of data 10, it is located ‘3 rd’ location is
called as, ‘Searching’.
3. Inserting :-
- This operation is used to adding a new record to the structure.
- Ex.: Data as 1, 5, 10, 7.
- We want to insert ‘20’ at ‘4th’ location after that output is 1, 5, 10,
20, 7.
4. Deleting :-
- This operation is used to removing a record from the structure.
- Ex.: Data as 1, 5, 10, 20, 7
- We want to delete data on ‘3rd’ location after delete output is 1,
5, 20, 7.

By:Chimle Mahesh 11 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

5. Sorting :-
- This operation is used to arrange the records in same logical
order.
6. Merging :-
- This operation is used to combining the records in two different
sorted fields into a single a sorted file.
7. Copying :-
- This operation is used to make the duplication of the record.
8. Concatenation :-
- This operation is used to combine any two records into single
record.

1.5 Notion and Concept of algorithm :-

The following summarizes certain basic conversation that are used in
writing algorithms.

1. Identifying Numbers :- Each algorithm is assign an identifying

number.
Ex.: Algorithm 4.3 refers to their third algorithm in chap. 4
2. Steps :- The steps of the algorithm are executed one by one starting
from step1.
3. Name of the Algorithm :- Every algorithm is given an identifying
name written in capital letters.
4. Introduction Comments :- Algorithm name is followed by a brief
description which input data, purpose and identifiers and variable
which are used in algorithm.

1. By:Chimle Mahesh 12 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

5. Comments :- Comment is a written in bracket which indicate the

purpose of the step.
6. Variable Name :- Variable name will use capital letters like ‘MAX’ or
‘DATA’. Single letter names of variables used as counters or subscripts
will also be capitalized in the algorithm and lower case may be used
for these variables in the mathematical description and analysis.
7. Assignment Statement :- Assignment statements will use the dots –
equal notation as :=.
Ex.: MAX := DATA [1]
Some text use the backward arrow () or equal to sign (=) for this
operation.
8. Input / Output :-
- Data element may be assign to the variable by read statement as
:- Read : variable name Ex.: Read : a
- Similarly, messages placed in quotation mark and data in
variables may be output by means of write as print statement
with following form.
Write : Messages or Variable name
Ex.: Write : “Have a nice day.”
Ex.: Write : MAX
9. Procedures :-
- The term ‘Procedure’ will be used for an independent
algorithmic module which solve a particular problem.
- The use of word ‘Procedure’ or ‘Module’ rather than
‘Algorithm’.

By:Chimle Mahesh 13 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

- The term procedure will also be used to describe a certain type

of sub algorithm.
10. Control Structures Statement :-
- Control may be transfer to any step ‘n’ of the algorithm by using
the goto statement as,
Ex.: “goto step n”
- There are following control structure or type of logic or flow of
control.
I. Sequence Logic / Sequential Flow.
II. Selection Logic / Conditional Flow.
III. Iteration Logic / Repetitive Flow.

I. Sequence Logic :- In this structure the modules are executed

sequentially.
II. Selection Logic :-
- In this structure a required module is get selected out of several
modules.
- The frequently used structure is if structure.
- Here end of the if structure by the statement :- [End of if
structure]
- The conditional structure are divided into three types.
i) Single Alternative. ii)
Double alternative. iii)
Multiple Alternative.
i) Single Alternative :- This structure has the form:

If Condition, Then :

1. By:Chimle Mahesh 14 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

[Module A]
[End of If structure]
ii) Double Alternative :- This structure has a form:

If Condition(1), Then :
[Module A]
Else :
[Module B]
[End of If structure]
iii) Multiple Alternative :- This structure has the form:

If condition(1), Then :
[Module A]
Else if condition (2),Then:
[Module A2]
. .
. .
Else if condition (n), Then:
[Module An]
Else [Module B]
[End of If structure]

III. Iteration Logic :-

- It includes loops. Here the end of loop is indicated at the end of
the structure by the statement:
[End of loop]
- In data structure generally repetitive loops are used as
following.
i) Repeat for …….. loop. ii)
Repeat while ….. loop.

By:Chimle Mahesh 15 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

i) Repeat for …… loop :-

- The repeat for …… loop uses an index variable, such as K, to
control the loop.
- The loop will usually have the form
Repeat for K = R to S by T
[Module]
[End of loop]
ii) Repeat while ….. loop :-
- The repeat while …. Loop uses a condition to control the loop.
- The loop will usually have the form:

Repeat while condition :

[Module]
[End of loop]

11. Exit Statement :- Exit statement is used to terminate algorithm.

12. Sub Algorithm :-
- A sub algorithm is an independently define algorithm.
- The algorithm is define separately from the main algorithm and
the purpose is to perform some complication when required
under control of the main algorithm.
- Sub algorithm receives values, called arguments from the main
algorithm and send back the result to the main algorithm.
- Sub algorithm may be call by many different algorithms, sub
algorithms or it may be called by itself recursively.
- Sub algorithms are classified into two basic categories that are,
(1) Function Sub Algorithm.
(2) Procedure Sub Algorithm.

1. By:Chimle Mahesh 16 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

(1) Function Sub Algorithm :-

- Function is used to return single value to the calling algorithm.
- Here transfer of control back and returning of the value are
perform by the statement : [Return (value)]
- The function begin as, : Function_name : NAME(PAR1, PAR2,
……, PARn)

(2) Procedure Sub Algorithm :-

- A procedure sub algorithm works similar to a function but
doesn’t return any value explicitly.
- Only control is transferred back to the calling algorithm by the
statement ‘return’.
- In procedure sub algorithm changed parameters are return to
the main algorithm automatically.
- A procedure begins as follows,
Procedure_Name :
NAME(PAR1, PAR2, ……. PARn)

1.6 ALGORITHMS: COMPLEXITY, TIME-SPACE TRADEOFF :-

- A well-defined list of steps for solving a particular problem is
called ‘Algorithm’.
- The most important use of these steps is to develop effective
algorithm for processing our data.

By:Chimle Mahesh 17 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

- The time and space are two important measurements which are
used to calculate the efficiency of an algorithm.
- The complexity of an algorithm is the function which gives the
running time and/or memory space used by the input size.
- There are two case usually investigates to find complexity.
1. Worst Case.
2. Average Case.
1. Worst Case :-
- The maximum value of F(n) for any possible input.
- C(n) = n is complexity of linear search algorithm.
2. Average Case :-
- The excepted value of F(n).

1. By:Chimle Mahesh 18 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

- Number ‘n’ is item in DATA, so no. of comparison can be any of

By:Chimle Mahesh 19 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

the no. 1, 2, 3, ………, n and each no. occurs in probability

then,

- In algorithm analysis different algorithms are compared by

calculating the efficiencies of these algorithms.
- Ex.: Consider an algorithm ‘A’ with ‘n’ size of the input data.
- The time is measure in terms of number of comparison perform
in sorting and searching.
- Space is measure by counting the maximum memory space
required to store given ‘n’ size of data. Hence, for algorithm a
complexity function c(n) which gives the running time and
storage space for into data size n.
- Following are the two algorithm they are compared using
complexity function.
- Suppose, we are given the name of the employee and we want to
find their telephone number.
- Here, telephone number may be easily display using one of the
following way.
1. Linear Search.
2. Binary Search.

1. By:Chimle Mahesh 20 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

1. Linear Search :-
- It is clear that time required execute the algorithm is
proportional to the number of comparisons performed by the
linearly.
- In this method each name of the file is get compared so the
average number of comparisons for the file with ‘n’ records is
equal to
- Hence, the complexity of linear search algorithm is

2. Binary Search :-
- In this method the name are stored in sorting order
alphabetically.
- This algorithm compare a given name with the name in the
middle of the list : This tells which half of the list the name
contain.
- Then compare name with the name in the middle of the correct
half to determine which quarter of the list contains name.
- Continue the process until finding name in the list. - Hence, the
complexity of the binary search method is c(n) = log 2n

1.8 Linear Array :-

A linear array is a list of finite number ‘n’ of similar type of data elements
such that
The element of an array are referenced by index set consisting of ‘n’
consecutive numbers.
The elements of an array are stored (placed) in successive memory location.

By:Chimle Mahesh 21 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

A number ‘n’ is called length or size of the array.

Suppose the index set consists of the integers 1, 2, 3, ……, n then the length
or the number of elements of an array can be obtained from the index set by
the formula.
length = UB – LB + 1
OR
length = UB (if LB = 1)

Here ‘UB’ is the largest index called upper bound and ‘LB’ is the lower bound
i.e. smallest index of an array.

DATA 30 15 35 40 50

LB 30 10 1 2 3
4 15
2 35
3 40
4 50
UB 5

length = UB – LB + 1
length =5–1+1 length= 4 – 0 + 1
=4+1 =4+1
=5 =5
- The element of an array may be denoted by the notation :

4. Subscript notation as :
A1, A2, A3, ……, An.
5. Parenthesis notation as:

1 .9 Representation of an Linear Array in Memory :- Consider

linear array LA stored in computer memory.
We know that the internal memory of a computer is a simply sequence
of addresses location as shown in following figure.

1. By:Chimle Mahesh 22 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

A(1), A(2), A(3), …….., A(n).

6. By the bracket notation as:
A[1], A[2], A[3], ……., A[n].

1000

1001

1002

1003

1004

Fig. Computer
Memory

In above representation computer doesn’t keep track of the address of

each element of an array.
If each keep track only the address of the first element of an array
because the elements of an array get stored in successive memory
cells.
Here the address of the first element of an array is represented by base
[LA] which is equal to 1000 and called base [LA] address of LA using
this base address computer calculate the address of any element K of
an array by using the formula as,

By:Chimle Mahesh 23 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

LOC [LA [K]] = Base [LA] + W [K – LB]

Here, ‘k’ is any location of ‘LA’. ‘W’ is the number of cells per word for
an array.
Ex.: W = 4 each indicate that it requires four cells of internal memory
to store each element.
Here, time require to access any element of an array at location ‘k’ is
cell because accessing is perform directly without scanning other
elements.
For determing internal memory location of ‘n’:
Consider an array DATA [10 : 80], suppose base address of DATA
i.e. Base [DATA] = 1000 and W = 4 words per cells for an array
element at location 12 is
LOC [DATA (k)] = Base [DATA] + W (k – LB)
LOC [DATA (12)] = 1000 + 4 (12 – 10)
= 1008
1.10 Traversing Linear Array :-
Suppose LA is the Linear Array used to store a list of elements in
computer memory.
To print each element of LA or count the number of elements of LA
traversing operation is use.
Accessing or processing each element of an array LA exactly once is
called “Traversing”.
Following is an algorithm which traverses a linear array LA.

Algorithm 1.1 : TRAVERS LA (LA, LB, UB, k)

Let LA is linear array with ‘n’ element, k is a counter,
variable LB is lower bound, UB is upper bound.
Step 1. : [Initialize counter k]

1. By:Chimle Mahesh 24 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

set k LB
Step 2. :
Repeat step 3 & 4 while
(k <= UB)

Step 3. : Apply PROCESS to LA[k]

Step 4. : [Increase counter k by 1]
set k k+1
[End of step 2 loop]
Step 5. : [Finished] Exit.

1.11 Inserting and Deleting Linear Array :-

- Let LA is a linear array used to store collection of data elements

in computer memory.
- Here, insertion operation is used to add a new element to an
array and deletion operation is used to remove any one of the
element from an array.
- If the allocation memory space for a linear array is large enough
the insertion operation of an element at the end of the linear
array can be perform easily then, the insertion of an element in
the middle of the linear array that means when one need to
insert a element middle of the array then on the average half of
the element must be moved downward to the new location so
that new element get inserted and also the order of other
elements get preserved.
- Similarly, an element at the end of the linear array may be
deleted easily than the element present in the middle of the

By:Chimle Mahesh 25 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

array that means for deletion of an element from the middle of

an linear array is difficult because each next element of an array
must be moved one location upward in order to fill up the array.
- Following is an algorithm to insert data element ITEM into the
kth position in a linear array LA.

Algorithm 1.2 : INSERTITEM (LA, k, n, ITEM)

Let LA is linear array with ‘n’ element, k is a positive
integer such that k <= nth algorithm perform insert
element ITEM into the kth position in LA.

Step 1. : [Initialize counter J]

set J N
Step 2. :
Repeat step 3 & 4
while J >= K
[Move Jth element
Step 3. :
downward]
set LA[J + 1] LA[J]
Step 4. : [decrease counter J by 1]
set J J–1
[End of step 2 loop]
Step 5. : [Insert element ITEM at location K]
set LA [K] ITEM
Step 6. : [Reset N]
set N N+1
Step 7. : [Finished] Exit.

Following is an algorithm delete the kth element from linear

array and assign it to variable ITEM.

1. By:Chimle Mahesh 26 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

Algorithm 1.3 : DELETEITEM (LA, K, N, ITEM)

Let LA is linear array with ‘n’ element, k is a positive
integer such that k <= N. The algorithm delete k th element
and store in ITEM.

Step 1. : [Store element of location K into ITEM]

set ITEM LA[K]
Step 2. :
[shift element upward] Repeat
for J K to N – 1

Step 3. : [Move J + 1 element upward]

set LA[J] LA[J + 1]
[End of step 2 loop]
Step 4. : [Reset N]
set N N–1
Step 5. : [Finished] Exit.

1.12 Searching Method :-

- Let a collection of data element are stored in computer memory
by using a linear array LA.
- In data structure searching operating is used to find the location
LOC of the given ITEM of information.
- Here a search is set to be successful or unsuccessful according to
weather ITEM is present or not (absent) in list.

By:Chimle Mahesh 27 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

- This method is depend on the type of data structure used to

maintain such list in memory.
- Normally operations like inserting, deleting and updating result
in data modification.
- This means that the operations inserting and deleting are used
to modify the data.
- Hence, these operations are closely related to searching.
- That is in deletion of an ITEM one must search for the location of
the ITEM and for insertion of an ITEM in the given list one must
search for the proper place.
- Here the operations insertion and deletion also required at
certain line which depend on the type of data structure used for
it.
- The complexity of searching algorithm is measured in term of
the number of comparison required to search an ITEM in given
list.
- In data structure particular element is search using one of the
following two searching methods.
I. Linear Search Method.
II. Binary Search Method.

I. Linear Search Method :-

- Let LA is a linear array with ‘n’ elements.
- The accurate way to search given ITEM in LA is to make
comparison of ITEM with each element of LA one by one i.e. first

1. By:Chimle Mahesh 28 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

test weather LA[1] = ITEM. Then last weather LA[2] = ITEM and
so on.
- The method which traverses LA sequentially to search ITEM is
called ‘Linear Search’ or ‘Sequential Search’.
- In this search, first the ITEM is stored at LA (N + 1) location as =
LA (N + 1) = ITEM.
- Then searching is started from the first element of the list, here
if ITEM is present at that time this search method display a
message successful search and if ITEM is not present in the list
then this search method display a message unsuccessful search
and reset the location variable LOC to Null or Zero.
- Following is a algorithm to find the location LOC of given
element ITEM for an array LA.

Algorithm 1.4 : LINERSRH (LA, LOC, N, ITEM)

Let LA is linear array with ‘N’ element and ITEM is a given
item of information. This algorithm perform finding the
location LOC of ITEM in LA or sets LOC = 0 if the search is
unsuccessful.

Step 1. :
[Insert ITEM at the end of the LA] set
LA (N + 1) ITEM
Step 2. : [Initialize counter location]
Set LOC 1
Step 3. : [Search for ITEM in LA]
Repeat step 4
while (LA [LOC] ITEM)

By:Chimle Mahesh 29 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

Step 4. : [Increase location LOC by 1]

LOC LOC + 1
[End of step 3 loop]
Step 5. : [Is search successful ?] If
LOC N + 1, Then
write “Unsuccessful search” and LOC
0 else write “Successful search a location
LOC”.
[End of if structure]
Step 6. : [Finished] Exit.

2. Binary Search Method :-

- Suppose LA is a linear array which is stored in increasing order

according to alphabetically.
- Binary search is an efficient algorithm method which find the
location LOC of the given item of information in the given array
LA.
- This method works as follows,
- Assign the pointer variable START and END denote starting and
ending locations of the elements in a list, i.e. START = 1 or LB
and END = N or UB.
- Calculate middle of the list and store it at pointer variable MID
as,
MID = INT [START + END] / 2

- Here INT [K] is used to obtain int value of K.

1. By:Chimle Mahesh 30 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

- Compare ITEM with middle element that means if ITEM = LA

[MID], then print a message search is “successful” and assign

value of MID to LOC as LOC = MID and exit.

- If ITEM LA [MID] then determine its proper half as :-

a. If ITEM < LA[MID], then ITEM can appear in the left half.
Hence to search ITEM in left half reset value of END as:
END = MID – 1 and repeat step 2.

b. If ITEM > LA[MID], then ITEM can appear in the right

half.
Hence to search ITEM in right half reset value of START
as:
START = MID+1 and repeat step 2.

- Here if there N elements, then this algorithm begins with

assigning START = 1 and END = N.
- The above steps 2–4 repeated still value of START < END.

- If an ITEM is not appear then algorithm assign LOC = Null (0)

value.
- It indicates that ITEM is not present

- Ex.: Consider a list to be sorted array LA of 14 elements.

LA : 10 11 20 22 30 33 40 44 50 55 60 66 70
77
- Apply the binary y search method to LA to search for value ITEM
= 44.

By:Chimle Mahesh 31 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

1.
10 11 20 22 30 33 40 44 50 55 60 66 70 77

1 2 3 4 5 6 7 8 9 10 11 12 13 14

After initializing START & END it becomes START = 1 &

END = 14
Then calculate the middle MID as,
MID = INT [SART + END] / 2
= INT [1 + 14] / 2
= INT [7]
MID = INT [7]
Hence, LA [MID] = 40

2. Since 44 > 40, START changes its value by,

START = MID + 1 =7+1 =
8
Hence, the list 44 50 55 60 66 70 77
become, 8 9 10 11 12 13 14

START = 8 & END = 14

Calculate the MID = INT [START + END] / 2
= INT [8 + 14] /2
= 11
LA [MID] = 11
2. Since, 44 < 60, END changes its value by END = MID – 1
= 11 – 1
= 10

1. By:Chimle Mahesh 32 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

Hence, the list 44 50 55 become,

8 9 10
Let, START = 8 & END = 10

calculate middle MID as,

MID = INT [START + END] / 2
= INT [8 + 10] / 2
=9
LA [MID] = 50
3. Since 44 < 50, END changes its value by, END = MID – 1
=9–1
=8
LA [MID] = 44
Let, START = 8 & END = 8

calculate middle MID as,

MID = INT [START + END] / 2
= INT [8 + 8] / 2
= INT [8]
LA [MID] 44

4. Since 44 = 44, search is successful at location LOC = MID i.e.

8.

Following is an algorithm binary search method.

Algorithm 1.5 : BINARYSRH (LA, LOC, N, MID, START, END,

ITEM)

By:Chimle Mahesh 33 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

Let LA is a sorted linear array with N element and ITEM is

a given information for which we have to make search.
The variable START,END,MID are the local pointer
variable used to stone location of beginning, ending and
middle element of the list respectively. This algorithm
perform finding the location LOC of ITEM in LA or sets
LOC = Null.

Step 1. : [Initialize pointer START & END]

set START = 1 or LB & END = N or UB.
Step 2. : Repeat step 3 & 4 or through 4
While START <= END
Step 3. : [Calculate Middle]
MID = INT [(START + END) / 2]
Step 4. : [Is element ITEM pointer in LA]
if [ITEM < LA(MID)], then
[END changes]
Set END=MID-1.
Else if ITEM > LA [MID], then
[START changes its value]
set START = MID + 1
else
write “Successful Search”
set LOC = MID and Exit
[End of if structure]
[End of step 2 loop]
Step 5. : [set LOC]

1. By:Chimle Mahesh 34 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

write “Unsuccessful search”

LOC = Null
Step 6. : Exit.

Complexity of Binary Search :-

In this algorithm there is deduction of half comparison the

total comparison require to locate certain ITEM are determine
using a complexity function F(N) as,
F(N) = [log2 N] + 1

By:Chimle Mahesh 35 / 35