Program For Binary Search By Iterative and Recursive way.

In Binary search algorithm, we are going to divide a given array into two parts and solve these parts iteratively.For this we are going to find mid element and compare it with element to be found. if it is found we are going to return position i.e(mid element). If element to be found is greater than mid then we are going to set lower bound to mid+1. If element to be found is less than mid then we are going to set upper bound to mid-1. 

Program By Iterative way:

#include<stdio.h>
void main()
{
   
    int arr[20],i,n;
    int h,l,mid,x;
    printf("Enter no. of elements");
    scanf("%d",&n);
    printf("\nEnter array Elements:");
    for(i=0;i<n;i++)
    {
        scanf("%d",&arr[i]);
    }
   
    printf("\nEnter no. to be searched:");
    scanf("%d",&x);
    l=0;
    h=n-1;
    mid=(l+h)/2;
    while(l<=h)
    {
        if(arr[mid]==x)
        {
            printf("\nElements found at %d Position\n",mid);
            break;   
        }
           
            if(x>arr[mid])   
            {
                l=mid+1;
            }
            if(x<arr[mid])
            {
                h=mid-1;
            }
       
    } 

}

Program:By Recursive Way

#include<stdio.h>
int main()
{
    int arr[20];
    int i,n;
    int h,l,mid,x;
    int result;
    printf("Enter number of elements:");
    scanf("%d",&n);
    printf("Enter array elements:");
    for(i=0;i<n;i++)
    {
        scanf("%d",&arr[i]);
    }
    l=0;
    h=n-1;
    printf("enter element to be searched:");
    scanf("%d",&x);
    result=BinarySearch(arr,l,h,x);
    printf("Element found at %d Position",result);
    return(0);

}
int BinarySearch(int arr[],int l,int h,int x)
{
    while(l<=h)
    {
        int mid=(l+h)/2;
        if(arr[mid]==x)
        {
            return(mid);
            break;
        }
        if(x>arr[mid])
        {
        return(BinarySearch(arr,mid+1,h,x));
        }
        if(x<arr[mid])
        {
            return(BinarySearch(arr,l,mid-1,x));
        }
    }
   
}

Note:

The Time Complexity By Iterative way is O(n).

The Time Complexity by Recursive way is  .

Worst Case,Best Case and Average Case Efficiency using Insertion Sort.

Insertion Sort is based on inserting a single element in the right for a given iteration.

#include<stdio.h>
void sortArray(int arr[],int n)
{
int i,temp,j;
for(i=0;i<n;i++)
{
temp=arr[i];
j=i-1;

while(j>=0 && arr[j]>temp)
{
arr[j+1]=arr[j];
j--;

}
arr[j+1]=temp;

}
}
void printArray(int arr[], int n)
{
   int i;
   for (i=0; i < n; i++)
       printf("%d ", arr[i]);
   printf("\n");
}

int main()
{
int i;
int arr[]={12, 11, 13, 5, 6};

int n=sizeof(arr);
printf("Given Array is:");
for(i=0;i<n;i++)
{
printf("%d\n",arr[i]);
}
sortArray(arr,n);
printArray(arr,n);
}

Explanation:

Best Case:If an input array is already Sorted. The time complexity will be O(n).
Worst Case:If the array is sorted in reverse order.In this case Time Complexity will be O(n2).
Average Case:If the input array consist of random numbers.The Time Complexity is O(n2).

Worst Case,Best Case and Average Case Efficiency using Linear Search.

Time complexities of any algorithm can be expressed by using best,Worst and Average case.
The Time Complexity of Linear Search is shown By using Program.

//Linear search program

#include<stdio.h>
int main()
{
int arr[]={1,10,30,40,50,60,77,56,57};
int x=57;
int n=sizeof(arr);
printf("Element %d is found at %d",x,search(arr,n,x));
return(0);

}
int search(int arr[],int n,int x)
{
int i;
for(i=0;i<n;i++)
{
if(arr[i]==x)
return(i);
}
return(-1);

}

Explanation:
// Worst case of this algorithm will be Θ(n) if element will be found at last position.
//For Average case,we have to search for all the inputs(taking sum of all inputs) and then divide it by no.of inputs.
i.e.

= Θ(n)

// Best case will occur when element will be found at first position.Best Case means how fast the algorithm can run