Practical No-1
Limitations of Array in C
Fixed Size and Memory Allocation in C
Lack of Dynamic Sizing
Absence of Bounds Checking
Homogeneous Data Types
Inefficient Insertions and Deletions
Fixed Data Alignment
Inflexible Sorting and Searching
Memory Fragmentation
Multidimensional Array Limitations
Compiler-Dependent Limitations
How Size of operator work with Array
size is the variable name that stores the size of the array, and datatype
specifies the type of data value stored in size.
sizeof(array_name) calculates the size of the array in bytes.
sizeof(array_name[index]) calculates the size of one element in the array.
The sizeof operator gives the amount of storage, in bytes, required to store an
object of the type of the operand. This operator allows you to avoid specifying
machine-dependent data sizes in your programs.
Syntax
datatype size = sizeof(array_name) /
sizeof(array_name[index]);
Practical No 2
Modification of linear search function
A linear search can be modified so that all instances in which the
target is found are returned. This change can be made by not
'breaking' when a match is found.
The linear search algorithm in C is going to be modified for the multiple
occurrences of the key element. The code is designed to find the number of
occurrences of the key element in the array along with their positions.
Time Complexity of Linear Search Algorithm:
Best Case Time Complexity of Linear Search Algorithm: O(1)
Best case is when the list or array’s first element matches the target element.
The time complexity is O(1) because there is just one comparison made. So
the best case complexity is O(1).
Best Case Time Complexity of Linear Search: O(1)
Average Case Time Complexity of Linear Search: O(N)
Worst Case Time Complexity of Linear Search: O(N)
Space Complexity of Linear Search: O(1)
Number of comparisons in Best Case: 1
Number of comparisons in Average Case: N/2 + N/(N+1)
Number of comparisons in Worst Case: N
Linear Search Algorithm:
Linear Search (Array A, Value x)
Step 1: Set i to 1
Step 2: if i > n, then jump to step 7
Step 3: if A[i] = x then jump to step 6
Step 4: Set i to i + 1
Step 5: Go to step 2
Step 6: Print element x found at index i and jump to step 8
Step 7: Print element not found
Step 8: Exit
Practical no 3
Modification of linear search function
A linear search can be modified so that all instances in which the
target is found are returned. This change can be made by not
‘breaking’ when a match is found.
For each element in the searchList
if element equal target value then
Add its index to a list of occurrences
if the list of occurrences is empty
raise ValueError
otherwise
return the list occurrences
Application of Linear Search :
Linear search has several practical applications in computer science and
beyond. Here are some examples:
Phonebook Search: Linear search can be used to search through a
phonebook to find a person’s name, given their phone number.
Spell Checkers: The algorithm compares each word in the document to
a dictionary of correctly spelled words until a match is found.
Finding Minimum and Maximum Values: Linear search can be used to
find the minimum and maximum values in an array or list.
Searching through unsorted data: Linear search is useful for searching
through unsorted data.
Practical no 4
Applications of Binary Search:
Searching in sorted arrays: Binary search is used to efficiently find an
element in a sorted array.
Database queries: Binary search can be used to quickly locate records in
a database table that is sorted by a specific key.
Finding the closest match: Binary search can be used to find the
closest value to a target value in a sorted list.
Interpolation search: Binary search can be used as a starting point for
interpolation search, which is an even faster search algorithm.
Difference Between Linear and Binary Search
parameter Linear Search Binary Search
Linear Search sequentially checks each Binary Search continuously divides the sorted
Definition element in the list until it finds a match or list, comparing the middle element with the
exhausts the list. target value.
The time complexity is O(n), where n is The time complexity is O(log n), making it
Time Complexity
the number of elements in the list. faster for larger datasets.
Less efficient, especially for large
Efficiency More efficient, especially for large datasets.
datasets.
Data
Does not require the list to be sorted. Requires the list to be sorted.
Requirement
Implementation Easier to implement. Requires a more complex implementation.
Eliminates half of the search space with each
Search Space Examines each element sequentially.
comparison.
Use Case Suitable for small and unsorted datasets. Ideal for large and sorted datasets.
Discuss and write the requirements for using binary search on an array
of numbers
Binary search works on sorted arrays. Binary search begins
by comparing an element in the middle of the array with the target
value. If the target value matches the element, its position in the array
is returned. If the target value is less than the element, the search
continues in the lower half of the array.
binary Search Algorithm
binary_Search( a, lower_bound, upper_bound, target)
Step 1: set start = lower_bound, end = upper_bound, pos = – 1
Step 2: repeat steps 3 and 4 while start <=end
Step 3: set mid = (start + end)/2 or start+(end-start)/2
Step 4: if a[mid] = target
set pos = mid
print pos
go to step 6
else if a[mid] > target
set end = mid – 1
else
set start = mid + 1
[end of if]
[end of loop]
Step 5: if pos = -1
print “Not Present”
[end of if]
Step 6: exit
Flowchart of Binary Search
