Coding Insertion Operation in Array in Data Structure
#include <stdio.h>
void display(int arr[], int n)
{
// code for traversal
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
int indInsertion(int arr[], int size, int element, int capacity, int index)
{
//code for Insertion
if (size >= capacity)
{
return -1;
}
for (int i = size - 1; i >= index; i--)
{
arr[i + 1] = arr[i];
}
arr[index] = element;
return 1;
}
int main()
{
int arr[100] = {7, 8, 12, 27, 88};
int size = 5, element = 45, index = 3;
display(arr, size);
indInsertion(arr, size, element, 100, index);
size++;
display(arr, size);
return 0;
}
#include <stdio.h>
void display(int arr[], int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
void indDeletion(int arr[], int size, int index)
{
for (int i = index; i < size-1; i++)
{
arr[i] = arr[i + 1];
}
}
int main()
{
int arr[100] = {7, 8, 12, 27, 88};
int size = 5, index = 2;
display(arr, size);
indDeletion(arr, size, index);
size--;
display(arr, size);
return 0;
}
Linear Search
This search method searches for an element by visiting all the elements sequentially until the element is found or the array finishes. It follows the array traversal method.
Linear search works for sorted as well as unsorted arrays.
Binary Search
This search method searches for an element by breaking the search space into half each time it finds the wrong element. This method is limited to a sorted array. The search continues towards either side of the mid, based on whether the element to be searched is lesser or greater than the mid element of the current search space.
Binary search works only on sorted arrays.
Comparision between linear search and binary search
Linear Search
Binary Search
Works on both sorted and unsorted arrays
Works only one sorted arrays
Equality operations
Inequality operations
O(n) WC complexity
O(log n) WC complexity
#include <stdio.h>
int linearSearch(int arr[], int size, int element)
{
for (int i = 0; i < size; i++)
{
if(arr[i]==element)
{
return i;
}
}
return -1;
}
int main()
{
int arr[]={1,3,5,56,4,3,23,5,4,54643,56,34};
int size = sizeof(arr)/sizeof(int); // gives size of array without hard coding
printf("The index where 5 is located is : %d",linearSearch(arr,size,5));
return 0;
}
#include <stdio.h>
int binarySearch(int arr[], int size, int element)
{
int mid, high, low;
low = 0;
high = size - 1;
// start seraching
while (low <= high) //keep search until low <= high
{
mid = (low + high) / 2;
if (arr[mid] == element)
{
return mid;
}
if (arr[mid] < element)
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
// search end
return -1;
}
int main()
{
int arr[] = {1, 3, 5, 56, 64, 73, 123, 225, 444}; // already sorted
int size = sizeof(arr) / sizeof(int);
printf("The index where 73 is located is : %d", binarySearch(arr, size, 73));
return 0;
}