Programming for Problem Solving(ESPP1) B.
TECH(Sem 1)
Unit 3 - Array techniques
ARRAY
An array is a linear data structure that stores a collection of elements of the same data type in
contiguous memory locations. Each element of an array can be accessed directly using its index.
Characteristics of an Array :
1. Homogeneity of Data
All elements stored in an array are of the same data type.
For example, an integer array can store only integer values, and a float array can store only
floating-point values. This property ensures uniformity in memory allocation and simplifies data
processing.
2. Contiguous Memory Allocation
Array elements are stored in consecutive memory locations.
If the base address of the array is known, the address of any element can be calculated using its
index. This property enables efficient and fast access to array elements.
3. Fixed Size Nature
The size of an array is specified at the time of declaration and cannot be altered during program
execution (for static arrays).
This fixed size characteristic can sometimes lead to memory wastage or insufficient memory
allocation.
4. Uniform Memory Size per Element
Each element of an array occupies the same amount of memory, which depends on the data type
of the array.
For example, in C language, each integer element generally occupies 4 bytes of memory.
One-Dimensional Array
A one-dimensional array is a linear data structure that stores a collection of homogeneous
elements in a single row. The elements are stored in contiguous memory locations and are
accessed using a single index value.
• It is a list of the variable of similar data types.
• It allows random access and all the elements can be accessed with the help of their index.
• The size of the array is fixed.
Programming for Problem Solving(ESPP1) [Link](Sem 1)
Syntax (in C) :
data_type array_name[size];
Example:
int marks[5];
Declaration
Declaration of a one-dimensional array specifies the data type, array name, and number
of elements to be stored.
Example:
float salary[10];
Initialization:
int num[5] = {10, 20, 30, 40, 50};
Accessing Elements
Array elements are accessed using the index number.
Example:
printf("%d", num[2]);
Programming for Problem Solving(ESPP1) [Link](Sem 1)
Output:
Two-Dimensional Array
A two-dimensional array is an array of arrays that stores data in the form of rows and columns,
also known as matrix representation. Each element is accessed using two indices, one for row
and one for column.
• It is a list of lists of the variable of the same data type.
• It also allows random access and all the elements can be accessed with the help of their
index.
• It can also be seen as a collection of 1D arrays. It is also known as the Matrix.
• Its dimension can be increased from 2 to 3 and 4 so on.
• They all are referred to as a multi-dimension array.
• The most common multidimensional array is a 2D array.
Syntax (in C) :
data_type array_name[row_size][column_size];
Example:
int matrix[3][3];
Declaration
Declaration of a two-dimensional array specifies the number of rows and columns.
Example:
int table[2][4];
Initialization:
int a[2][3] = {1, 2, 3, 4, 5, 6};
Programming for Problem Solving(ESPP1) [Link](Sem 1)
Accessing Elements
Elements are accessed using row and column indices.
Example:
printf("%d", a[1][2]);
Programming for Problem Solving(ESPP1) [Link](Sem 1)
Output:
Array as homogeneous collection of elements :
An array is defined as a homogeneous collection of elements because all the elements stored in
an array are of the same data type and are placed in contiguous memory locations.
An array is a linear data structure that stores a homogeneous collection of data elements under a
single name, where each element is identified by a unique index or subscript.
Homogeneous Collection of Element
• Homogeneous means similar or of the same type.
• In an array, every element must belong to one common data type such as int, float, or
char.
• This uniformity allows the compiler to allocate equal memory space for each element and
enables efficient access using index values.
Reversing Elements of an Array
Reversing an array means rearranging the elements of the array in such a way that the first
element becomes the last, the second element becomes the second last, and so on. After
reversing, the order of elements becomes exactly opposite to the original order.
Array reversal is the process of interchanging the positions of elements of an array so that
the element at index i is swapped with the element at index (n − 1 − i), where n is the size of the
array.
If the original array is:
A = [10, 20, 30, 40, 50]
After reversing, the array becomes:
A = [50, 40, 30, 20, 10]
Purpose of Reversing an Array
1. To process data in reverse order.
2. To simplify certain algorithms such as searching and sorting.
3. To modify the arrangement of data for problem-solving.
4. Used as a basic operation in data structure manipulation.
Programming for Problem Solving(ESPP1) [Link](Sem 1)
Program to Reverse an array
Programming for Problem Solving(ESPP1) [Link](Sem 1)
Searching problems:
Searching -
Searching is a fundamental operation that refers to the process of locating a particular
element (key) in a collection of [Link] the element is found, the search is said to be
successful; otherwise, it is unsuccessful.
Searching techniques are mainly classified into:
1. Linear Search
2. Binary Search
Linear Search:
Linear search is a simple searching technique in which the elements of a list or array are
examined one by one sequentially until the desired element is found or the list ends. In
linear search, the search operation proceeds from the beginning of the data structure to
the end, without skipping any element, hence it is also known as sequential search.
Characteristics
• Does not require the data to be sorted.
• Elements are checked from the first position to the last.
• Suitable for small data sets.
• Simple to understand and implement.
Algorithm
1. Start from the first element of the array.
2. Compare the search key with the current element.
3. If the element matches the key, return its position.
4. If not, move to the next element.
5. Repeat the process until the element is found or the array ends.
Time Complexity
• Best Case: O(1) (element found at first position)
• Worst Case: O(n) (element found at last position or not found)
• Average Case: O(n)
Programming for Problem Solving(ESPP1) [Link](Sem 1)
Program for Linear Search
Output:
Programming for Problem Solving(ESPP1) [Link](Sem 1)
Binary Search:
Binary search is an efficient searching technique that works on a sorted array by
repeatedly dividing the search interval into two halves. The data must be sorted in
ascending or descending order. Binary search is an efficient searching algorithm that
compares the search key with the middle element of a sorted array and reduces the search
space by half at each step. In binary search, the search operation begins at the middle of
the list and proceeds either to the left or right sub-list depending on the comparison result.
Characteristics
• Uses the divide and conquer approach.
• Reduces search space by half in each step.
• Faster than linear search for large data sets.
Algorithm
• Set low to the first index and high to the last index.
• Calculate mid = (low + high) / 2.
• Compare the search key with the middle element.
• If equal, the element is found.
• If key is smaller, set high = mid - 1.
• If key is greater, set low = mid + 1.
• Repeat until low exceeds high.
Programming for Problem Solving(ESPP1) [Link](Sem 1)
Program for Binary Search
Output: