Data Structures and Algorithms Analysis: Arrays

DATA STRUCTURES and
ALGORITHMS ANALYSIS
ARRAYS
Data Structure: Definition
It is a collection of related data and a set of rules
for organizing and accessing it.
The study of data structures involves the identification

and development of useful mathematical entities and
operations and the determination of classes of problems
that can solved by these entities and operations.
• The choice of data structure affects the
operations that can be done on the data.
Example: List of family members.

Can:
Sort the names alphabetically
Determine whether or not a given name is in
the family
Example: List of family members.
Can:
Find the members with the longest and
shortest names
Can’t:
х Determine the relationship of any two members
in the family
Arrays
An array is a structure consisting of a fixed
number of components with each component of
the same type.
 The primary characteristics of an array are its name,

component type, and indices of the first and last
components.
 One-Dimensional – Simplest
 Multidimensional – Generalization
Arrays: One-Dimensional
An element of an array found in position p
where p is any value from 0 to n-1 can be
directly accessed by using the identifier
arrayname [p].
One advantage of the array is that each element
found in the array can be accessed directly.
Array Search
1. Sequential Search
Works for both sorted and unsorted data.
Uses a pointer and sets the value of this
initially to the first element. The value of the
pointer is increased by 1 until the element is
found or the end of the array is reached.
Array: Sequential Search
Illustration:
0 1 2 3 4 5 6 7 8 9
A 10 40 50 5 15 1 43 12 23 0
ptr
Assumptions:
A – array name (int type)
ptr – int variable that controls the index
n – size of the array
x – element to be searched (int type)
*** The elements of the array are unique
Array: Sequential Search
Illustration:
0 1 2 3 4 5 6 7 8 9
A 10 40 50 5 15 1 43 12 23 0
ptr
Procedure:
ptr = 0;
while(A[ptr]!=x && ptr<n)
ptr++;
Array Search
2. Binary Search
The data is “halved” at each step of the execution
– meaning, the midway observation of the
section of the array to be searched is used to
compare with the value of the element being
searched.
If the element being searched is greater than the
midway element, then the element (if ever it is in
the array) may exist at the right of the midway
element – never to the left, if the array is sorted
in ascending order.
Array Search
2. Binary Search
Searching is to be done again, but this time, on
the section (which is already “halved”) where the
observation may possibly exist.
The process of locating the midway element in
the constantly “halved” section continues until
the observation is found or the index of the
leftmost element of the sub-array exceeds the
index of the rightmost element of the sub-array.
Array: Binary Search
Illustration:
0 1 2 3 4 5 6 7 8 9
A 0 1 5 10 12 25 43 90 92 99
lower middle upper

Assumptions:
A – array name (int type)
lower, middle, upper – int variables that control the index
n – size of the array
x – element to be searched (int type)
*** The elements of the array are unique
Array: Binary Search
Procedure:
lower = 0;
upper = n – 1;
middle = (lower+upper)/2;
while(A[middle]!=x && lower<upper)
{
if(x > A[middle])
lower = middle + 1;
else
upper = middle – 1;
middle = (lower+upper)/2;
}
Assignment:
1. Write a procedure for sorting the elements of a
one-dimensional array.
2. Write a procedure for counting every
occurrence of the element being searched.
(Sequential search)
Assumption: the elements are not unique.
Multidimensional Arrays
• Although the memory of a computer is one-
dimensional, a user can define and manipulate
directly a multidimensional array.
• The idea is that most programming languages
provide this facility directly and the mapping of
multidimensional arrays to one-dimensional
arrays is implemented transparently from the
user.
Example:
M[3][2]
Usually,
first index – row
second index – column
• As in one-dimensional arrays, the elements of a

multidimensional array can be accessed directly
Searching a two-dimensional array:
1. Increase the row number faster than the
column number (searches the matrix
horizontally, from top to bottom)
2. Increase the column number faster than the
row number (searches the matrix vertically,
from left to right)
Exercises:
1. Write a procedure for inserting a new
element x into a sorted array A of size n.
2. Given a square matrix which is stored in a
two-dimensional array. Check if the matrix
is symmetrical about the main diagonal.
Graded Exercise - Arrays
Write a program that will ask for integer inputs
into a 5 x 5 array. Your program shall evaluate if
the array is triangular, i.e. every element below
OR above the main diagonal is zero, or not.
Allotted Time: 1 Hour

Data Structures and Algorithms Analysis: Arrays

Uploaded by

Copyright:

Available Formats

Data Structures and Algorithms Analysis: Arrays

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Data Structures and Algorithms Analysis: Arrays

Uploaded by

Copyright:

Available Formats

DATA STRUCTURES and

The study of data structures involves the identification

Example: List of family members.

 The primary characteristics of an array are its name,

lower middle upper

• As in one-dimensional arrays, the elements of a

Allotted Time: 1 Hour

You might also like