Binary search of an ordered list of integers

Binary search is a fundamental algorithm in computer science. It is used to find the position of a given integer in a sorted list of integers. We don't have to iterate through the whole list, if we use this algorithm. Therefore it is an efficient algorithm for searching. The complexity of binary search algorithm is O(logN). 

http://interactivepython.org/runestone/static/pythonds/SortSearch/TheBinarySearch.html

If N elements are there in the list, 
you will have to halve the list x times to find an element. (Halve the list until 1 element is left)

 1 = N / 2^x
 2^x = N
 x = log₂ N

Therefore time complexity - O(logN)

[code]
#include <stdio.h>

int main()
{
    int arr[100];
    int n, i, el;

    printf("Enter the number of elements: ");
    scanf("%d",&n);

    printf("Enter the elements\n");
    for(i = 0; i<n; i++)
    {
        scanf("%d",&arr[i]);
        if(i != 0 && arr[i-1]>arr[i])
        {
            printf("Please enter a sorted list!\n");
            return 0;
        }
    }

    printf("Enter the element to search\n");
    scanf("%d",&el);

    int position = binarySearch(arr,n,el);
   
    if(position != -1)
        printf("The element is at %d.\n",position);
    else
        printf("Element not found!\n");

    return 0;
}

/*Binary search function
  Arguments - integer array
          size of the array
          element to search for
  Return the position if successful
 
*/
int binarySearch(int arr[], int size, int el)
{
    int low = 0, high = size-1;
    int mid = (high + low)/2;

    while(arr[mid] != el)
    {
        if(arr[mid] > el)
            high = mid;
        else
            low = mid;

        if(high == low+1)
        {
            if(arr[high] == el)
                return high;
            else if(arr[low] == el)
                return low;
            else
                return -1;
        }
        mid = (low + high)/2;
    }
    return mid+1;
}[/code]

Stack data structure implemented in C

Stack

A stack is a container of objects that are inserted and removed according to the last-in first-out (LIFO) principle. Only two operations are allowed in a stack:

• Push the item into the stack
• Pop the item out of the stack

A stack is a limited access data structure - elements can be added and removed from the stack only at the top.

Following is an implementation of a stack in C

stack.h file contains all the implementations related to the stack. Please find a link on github.com for the same implementation below at the bottom.

[code]#include <stdlib.h>
#include <limits.h>

//functions and data structure are implemented in the header file

typedef struct node
{
    int pos;
    int data[SIZE];
   
}stack_node;

typedef stack_node* stack_ref;

//create a new stack
stack_ref stackCreate()
{
    stack_ref ref = malloc(sizeof(stack_node));
    (*ref).pos = 0;
    return ref;
}

//destroy an existing stack
int stackDestroy(stack_ref st)
{
    if(st != NULL)
    {
        free(st);
        return 1;
    }
    return 0;
}

//add a new element
int stackPush(stack_ref st,int el)
{
    if(!StackIsFull(st))
    {       
        (*st).data[(*st).pos] = el;
        (*st).pos++;
        return 1;
    }

    return 0;
}

//remove the last element
int stackPop(stack_ref st)
{
    if(StackIsEmpty(st))
    {
        return INT_MIN;
    }   
    (*st).pos--;
    return (*st).data[(*st).pos];
}

//peek at the top element
int stackPeak(stack_ref st)
{
    if(StackIsEmpty(st))
    {
        return INT_MIN;
    }   
    return (*st).data[(*st).pos-1];
}

//if stack is empty
int StackIsEmpty(stack_ref st)
{
    if((*st).pos == 0)
        return 1;
    return 0;
}

//if stack is full
int StackIsFull(stack_ref st)
{
    if((*st).pos == SIZE)
        return 1;
    return 0;
}
[/code]

reverse_string.c file is an example of how a stack can be used.

[code]

//define the stack size here
#define SIZE 50

#include <stdio.h>
#include "stack.h"
#include <string.h>


int main()
{
    char string[SIZE];
    char reverse[SIZE];
    int i,j;
   
    printf("Enter the string to reverse: \n");
    fgets(string, SIZE, stdin);
   
    //create stack for the string
    stack_ref st = stackCreate();
   
    for(i = 0; i<strlen(string); i++)
        stackPush(st, (int)string[i]); 
   
    for(i = 0; i<strlen(string); i++)
        reverse[i] = (char)stackPop(st);
   
    reverse[i] = 0;
   
    printf("Reversed string: %s\n",reverse);
    return 0;
}[/code]

Please visit here to view the code in github.com

Socket Programming - Simple UDP client and server programs. ( In C)

UDP

UDP is a simple transport-layer protocol. The application writes a message to a UDP socket, which is then encapsulated in a UDP datagram, which is further encapsulated in an IP datagram, which is sent to the destination.  
There is no guarantee that a UDP will reach the destination, that the order of the datagrams will be preserved across the network or that datagrams arrive only once. 

Server

1. Listen for a client's requests.
2. Process the requests.
3. Return the results back to the client. 

Client

1. Send the request to the server.
2. Wait for the server's response.

Server Program

[code]

#include <sys/socket.h>
#include <netinet/in.h>
#include <strings.h>
#include <stdio.h>

int main(int argc, char**argv)
{
    int sockfd,n;
    struct sockaddr_in servaddr, cliaddr;
    socklen_t len;
    char mes[1000];
    char send[] = "Hello client!";
   
    sockfd=socket(AF_INET,SOCK_DGRAM,0);
   
    servaddr.sin_family = AF_INET;   
    servaddr.sin_addr.s_addr=htonl(INADDR_ANY);
    servaddr.sin_port=htons(32000);
   
    bind(sockfd,(struct sockaddr *)&servaddr,sizeof(servaddr));
    len = sizeof(cliaddr);
   
    while(1)
    {
        n=recvfrom(sockfd,mes,1000,0,(struct sockaddr*)&cliaddr,&len);
   
        sendto(sockfd,send,n,0,(struct sockaddr*)&cliaddr,sizeof(cliaddr));
        mes[n] = 0;
   
        printf("Client says: %s\n",mes);
    }   
    return 0;
}[/code]

Client Program

[code]

#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <stdio.h>
#include <string.h>


int main(int argc, char**argv)
{
    int sockfd,n;
    struct sockaddr_in servaddr;
    char send[] = "Hello server!";
    char recv[1000];

    if (argc != 2)
    {
        printf("usage:%s <IP address>\n",argv[0]);
        return -1;
    }
   
    sockfd=socket(AF_INET,SOCK_DGRAM,0);
    bzero(&servaddr,sizeof(servaddr));

    servaddr.sin_family = AF_INET;
    servaddr.sin_addr.s_addr=inet_addr(argv[1]);
    servaddr.sin_port=htons(32000);

    sendto(sockfd,send,strlen(send),0,(struct sockaddr*)&servaddr,sizeof(servaddr));

    n=recvfrom(sockfd,recv,10000,0,NULL,NULL);

    recv[n]=0;
   
    printf("Server says: %s\n",recv);
    return 0;
}[/code]