Implementing Binary Search Algorithm in C++/C

BinarySearch method implements binary search algorithm. This method you can use in C/C++ program. Method takes integer array, array start position, array last element position, and value to search as input. Method returns position of the value to search in the array, if value not found then it returns -1. As we know binary search algorithm can only be used for sorted arrays. In case if you wish to use binary search on an array which is not sorted then you must sort it using some sorting technique and then use binary search algorithm to find the desired element in the array. 

int BinarySearch( int * intArray, int start, int end, int key) {     while( start <= end )     {         int mid = (start + end)/2;            if( intArray[mid] == key)             return mid;         if( key < intArray[mid]  )             end = mid - 1;         else             start = mid + 1;     }     return -1; }

Binary search can also be implemented in recursive way as below. 

int RecBinarySearch( int * intArray, int start, int end, int key) {     if( start <= end )     {         int mid = (start + end)/2;            if( intArray[mid] == key)         {             return mid;         }         else         {             if( key < intArray[mid]  )                 return    RecBinarySearch( intArray, start, mid-1, key);             else                 return RecBinarySearch( intArray, mid+1, end, key);         }     }     else         return -1; // Element not Found }

Implementing Merge Sort Algorithm in C/C++

Below function implements the Merge Sort algorithm. The function takes input as a array of integers start and end position of the array. Merge Sort  uses the Divide and Conquer method for sorting the array. 

MergeSort method divides the array and Merge method merges sorted array in sorted fashion.

void MergeSort( int * intArray, int start, int end) { if( start < end ) { int mid = (end + start)/2; Sort( intArray, start, mid ); Sort( intArray, mid+1, end ); Merge( intArray, start, mid, end); } } void Merge( int * intArray, int start, int mid, int end) {     int mid2 = mid +1;     int nFirst = (mid - start)  + 1;     int nSec= (end - mid);     int * pLeft = new int [nFirst + 1];         int * pRight = new int [nSec + 1];          for ( int cntr1= 0; cntr1 < nFirst ; ++ cntr1)     {         pLeft[cntr1] = intArray[start + cntr1];     }         pLeft[nFirst] = intArray[mid] + intArray[end];          for ( int cntr1 = 0; cntr1 < nSec ; ++ cntr1)     {         pRight[cntr1] = intArray[mid2 + cntr1];     }     pRight[nSec] = intArray[mid] + intArray[end];          for( int cntr = start, j = 0, k = 0; cntr <= end ; )     {         if( pLeft[j] < pRight[k] )         {             intArray[cntr++] = pLeft[j++];             continue;         }                 intArray[cntr++] = pRight[k++];     }     delete [] pLeft;     delete [] pRight; }

Merge method can write such as stop once either array left or right has had all its elements copied back to intArray then copy the reminder other array back to intArray as given below.

void Merge( int * intArray, int start, int mid, int end) {     int mid2 = mid +1;     int nFirst = (mid - start)  + 1;     int nSec= (end - mid);     int *pLeft = new int [nFirst];       int *pRight = new int [nSec];        for ( int cntr1= 0; cntr1 < nFirst ; ++ cntr1)     {         pLeft[cntr1] = intArray[start + cntr1];     }            for ( int cntr1 = 0; cntr1 < nSec ; ++ cntr1)     {         pRight[cntr1] = intArray[mid2 + cntr1];     }     int cntr = start, j = 0, k = 0;     for( ; j < nFirst && k < nSec ; )     {         if( pLeft[j] < pRight[k] )         {             intArray[cntr++] = pLeft[j++];         }                else         {             intArray[cntr++] = pRight[k++];         }     }     for( ; j < nFirst ; j++)     {         intArray[cntr++] = pLeft[j];     }     for( ; k < nSec ; k++)     {         intArray[cntr++] = pRight[k];     }     delete [] pLeft;     delete [] pRight; }

You can even use insertion sort to sort and merge the array as shown below. 

void Merge( int * intArray, int start, int mid, int end) {     for( int nCtr = mid+1; nCtr <= end; nCtr++)     {         int n = nCtr - 1;         int key = intArray[nCtr];         while( n >= start && intArray[n] > key  )         {             intArray[n+1] = intArray[n];             n--;         }         intArray[n+1] = key;     } }

Reversing singly Link List

Consider you have a single link list as below:

4 -> 8 -> 1 -> NULL

and you want to reverse this list as

1 -> 8 -> 4 -> NULL

In order to reverse the list we have to make the next pointer of your node to point to earlier element in the list as below.

Original List:

4 -> 8 -> 1 -> NULL

Reversed List:

NULL <- 4 <- 8 <- 1

Now how can we make this happen. Remove one element at a time from the original list and put it to new list at the beginning as shown below.

Original List:

4 -> 8 -> 1 -> NULL

New two lists:

4 ->NULL     &  8 -> 1 -> NULL

Here we are not allocating any memory using new for new list, we have just dis-joined it from original list, follow same steps till end and you are done.

Original List:

4 -> 8 -> 1 -> NULL

New two lists:

8 -> 4 ->NULL     &  1 -> NULL

Original List:

4 -> 8 -> 1 -> NULL

New lists:

1 -> 8 -> 4 ->NULL

Following is the code for the above mentioned :

Node * ReverseList(Node * pHead) {     if (pHead)     {         Node * pLastNode = NULL;         while (pHead)         {             Node * pTemp = pHead->pNext;             pHead->pNext = pLastNode;             pLastNode = pHead;             pHead = pTemp;         }         return pLastNode;     }     return NULL; }

Here Node is struct of type: 

struct Node

{ 

    int data;  //This can be any data type

    Node * Next; 

};

Implementing Insertion sort in C/C++

Below function implements the insertion sort algorithm. The function takes input as a array of integers and size of the array.
The sorting is performed in place. 


void InsertionSort(int * array, int size)
{
    //we are starting from second element of the array
    for(int counter = 1; counter < size; counter++)
    {
        int nKey = array[counter];
        int tempCounter = counter-1;
        while(tempCounter >= 0 && array[tempCounter] > nKey )
        {           
            array[tempCounter+1] = array[tempCounter];
            tempCounter--;
        }
        array[tempCounter+1] = nKey;       
    }
}

Finding Middle node of the singly link list with recursion

You could find middle of the single linked list in multiple ways :

1. Simple traverse whole list once to count number of nodes in the list, then again traverse till mid element.
2. Use two list pointers, in one pass increment first list pointer by two nodes and second list pointer by one node, this way when first list pointer will reach to end of list our second pointer will be pointing to the middle of the list.
3. Use recursion to find mid.

Here we will discuss how  to reach till the mid using recursion:

To find mid you will require two things, one number elements and second how many elements we have traversed. This can be achieved using two variables one will keep track of at which element we are and one will count number of nodes till end.

int FindMid(Node * head, int nNumberOfNode = 0)

{

      if( NULL == head )

      {

            return 0;

      }

      ++ nNumberOfNode;

      int nNodeBackTraverced = FindMid(head->next, nNumberOfNode);

      if( (nNodeBackTraverced == (nNumberOfNode - 1)) || (nNodeBackTraverced  == nNumberOfNode) )

            cout << "Mid Node data: " << head->data << endl;

      return ++nNodeBackTraverced;

}

The or condition in the if will take care of both, Odd number of nodes as well as even number of nodes.