Wednesday, March 5, 2014

Binary Search Sorted Int Array Recursively

There exists a recursive solution for the binary search algorithm. At each step lower and higher bounds for the search interval are updated and the search key is scanned in this new updated interval.
For recursive binary search implementation; search interval is updated depending on the midPoint value.

midPoint = lowerBound+(higherBound-lowerBound)/2

For the starting step; lowerBound is 0 and higherBound is the last array index.

Following sample project created by qt creator and contains following files:
1- SearchIntArrayRecursively.pro
2- main.cpp


SearchIntArrayRecursively.pro file contains project configuration.

TEMPLATE = app
CONFIG += console
CONFIG -= app_bundle
CONFIG -= qt
SOURCES += main.cpp

main.cpp file contains main method and recursive binarySearch function implementations.

#include <stdio.h>

int getIndexOfItemRecursively(int pSearchedItem, int* pArray, int mLowerBound, int mHigherBound)
{
    if( mLowerBound > mHigherBound )
        return -1;
    int midIndex = mLowerBound+(mHigherBound-mLowerBound)/2;

    if( pSearchedItem < pArray[midIndex] )
        return getIndexOfItemRecursively(pSearchedItem, pArray, mLowerBound, midIndex-1);
    else if(pSearchedItem>pArray[midIndex])
        return getIndexOfItemRecursively(pSearchedItem, pArray, midIndex+1, mHigherBound );
    else
        return midIndex;
}

int findIndexOfItem( int pSearchedItem, int* pArray, int pTotalItemCount )
{
    return getIndexOfItemRecursively(pSearchedItem, pArray, 0, pTotalItemCount-1);
}

int main(int argc, char* argv[])
{
    int mArray[] = {1, 2, 4, 12, 34, 45, 56, 67, 78, 89, 90};
    int mLengthOfArray = sizeof(mArray)/sizeof(int);
    printf("There are %d items in the array\n", mLengthOfArray);
    printf("Items :\n");
    for(int i = 0; i<mLengthOfArray; i++)
    {
        if( i!=mLengthOfArray-1 )
            printf("%d,", mArray[i]);
        else
            printf("%d\n", mArray[i]);
    }
    printf("Indexes :\n");
    for(int i = 0; i<mLengthOfArray; i++)
    {
        if( i!=mLengthOfArray-1 )
            printf("%d,", i);
        else
            printf("%d\n\n", i);
    }
    int mSearchItem = 12;
    int mIndex = findIndexOfItem( mSearchItem, mArray, mLengthOfArray );
    if( mIndex!=-1 )
        printf("Item %d is at index %d\n", mSearchItem, mIndex);
    else
        printf("Item %d not found in the array\n",mSearchItem);

    mSearchItem = 89;
    mIndex = findIndexOfItem( mSearchItem, mArray, mLengthOfArray );
    if( mIndex!=-1 )
        printf("Item %d is at index %d\n", mSearchItem, mIndex);
    else
        printf("Item %d not found in the array\n",mSearchItem);

    mSearchItem = 91;
    mIndex = findIndexOfItem( mSearchItem, mArray, mLengthOfArray );
    if( mIndex!=-1 )
        printf("Item %d is at index %d\n", mSearchItem, mIndex);
    else
        printf("Item %d not found in the array\n",mSearchItem);

    return 0;
}

We can analyze the steps for the first search item 12.



Search for 12 :

  • Find midPoint. For this case midPoint is at index 5. If the searchItem (12) is less than the item at index midPoint (45) then update higherBound value with midpoint-1.
  • Search in the new range with new higherBound value. higherBound is now midPoint-1. And lowerBound is 0.
New Sub Array Shrinks To 5 Items:

  • Find midPoint. For this case midPoint is at index 2. If the searchItem is higher than the item at index midPoint then update lowerBound value with midpoint+1.
  • Search in the new range with new lowerBound value. lowerBound is now midpoint+1 and higherBound does not change for this case.
New Sub Array Shrinks To 2 Items :
  • Find midPoint. For this case midPoint is at index 3.
  • SearchedItem is not less than the item at midPoint.
  • SearchedItem is not higher than the item at midPoint.
  • Then item is at midPoint. Return index of midPoint.

When you run the above recursive binary search sample following console output is generated :


Tuesday, February 25, 2014

Binary Search Sorted Int Array Iteratively

Binary Search is one of the most widely known search algorithms. One of the main restrictions to use binary search for existing sets is that your list or container must be sorted before searching inside it.
Instead of searching a list or container by using linear-search algorithm, item-by-item, binary search is considered more efficient in terms of time and space.

Following sample project created by qt creator and contains following files:
1- SearchIntArray.pro
2- main.cpp

SearchIntArray.pro file contains project configuration.
CONFIG += console
TEMPLATE = app
SOURCES += main.cpp
main.cpp file contains main method and indexOfItem function implementations.
#include <stdio.h>

int indexOfItem(int pSearchedtem,int* pArray,int pTotalItemCount)
{
    int mLowerBound = 0;
    int mHigherBound = pTotalItemCount-1;

    while( mLowerBound<= mHigherBound )
    {
        int midIndex = mLowerBound+(mHigherBound-mLowerBound)/2;
        if( pSearchedtem < pArray[midIndex] )
            mHigherBound = midIndex-1;
        else if(pSearchedtem>pArray[midIndex])
            mLowerBound = midIndex+1;
        else
            return midIndex;
    }

    return -1;
}

int main(int argc, char* argv[])
{
    int mArray[] = {1, 2, 4, 12, 34, 45, 56, 67, 78, 89, 90};
    int mLengthOfArray = sizeof(mArray)/sizeof(int);
    printf("There are %d items in the array\n", mLengthOfArray);
    printf("Items :\n");
    for(int i = 0; i<mLengthOfArray; i++)
    {
        if( i!=mLengthOfArray-1 )
            printf("%d,", mArray[i]);
        else
            printf("%d\n", mArray[i]);
    }
    printf("Indexes :\n");
    for(int i = 0; i<mLengthOfArray; i++)
    {
        if( i!=mLengthOfArray-1 )
            printf("%d,", i);
        else
            printf("%d\n\n", i);
    }
    int mSearchItem = 12;
    int mIndex = indexOfItem(mSearchItem,mArray,mLengthOfArray);
    if( mIndex!=-1 )
        printf("Item %d is at index %d\n", mSearchItem, mIndex);
    else
        printf("Item %d not found in the array\n",mSearchItem);

    mSearchItem = 89;
    mIndex = indexOfItem(mSearchItem,mArray,mLengthOfArray);
    if( mIndex!=-1 )
        printf("Item %d is at index %d\n", mSearchItem, mIndex);
    else
        printf("Item %d not found in the array\n",mSearchItem);

    mSearchItem = 91;
    mIndex = indexOfItem(mSearchItem,mArray,mLengthOfArray);
    if( mIndex!=-1 )
        printf("Item %d is at index %d\n", mSearchItem, mIndex);
    else
        printf("Item %d not found in the array\n",mSearchItem);

    return 0;
}

indexOfItem function implements binary search algorithm in C programming language iteratively. indexOfItem function takes the item to search for inside the array as one of its incoming parameters and function returns the index of the found item or -1 if not was found.

Binary Search algorithm, as described at http://algs4.cs.princeton.edu/home/ ,
         
             - lowerBound = 0
             - higherBound = itemCount-1
             - loop until lowerBound is less than or equal to the upper bound
                       - divides the sorted container into 2 parts at the center, find middle index
                       - compares the searchKey with the the item which is at the middle index
                               - if the searchKey is greater than the item which is at the middle index
                                                     - then update the lower bound for search with (middle index+1)
                               - else if the searchKey is lower than the item which is at the middle index
                                                     - then update the upper bound for search with (middle index-1)
                               - else
                                       - then the searchKey is the item which is at the middle index
            - end loop
            return indexNotFound

main function contains 3 test-cases for binary search algorithm. First 2 searchKeys (12 and 89) are found in the test array whereas the last searchKey (91) is not found in the list.

Console output contains all the printf function results as follows :


Wednesday, February 12, 2014

Virtual Functions and Inheritance

Inheritance helps to reduce the amount of code written or repeated by using a base-derived relation in object-oriented-world. Common functions are collected in a base class and the derived class extends or directly uses the existing base class functions. In some situations base class also can be pointing to different derived classes depending on the run-time behavior.

When base class is used to point to derived class, base class pointer calls overridden base-class methods, if there are any base class virtual method re-implementations in the derived class. Virtual functions in C++ help to transfer a specific behavior in the base class to derived class by declaring the function virtual in the base class. Derived is free to re-implement base class virtual functions.

If the derived class does not provide any implementation for the base class virtual functions then the base class virtual functions are called. This is not always the expected behavior because base class virtual functions are declared to be overridden in the derived class.

Following sample project created by qt creator and contains following files:
1- VirtualFunctions.pro
2- main.cpp
3- abstractservice.h
4- abstractservice.cpp
5- activityservice.h
6- activityservice.cpp
7- userservice.h
8- userservice.cpp



VirtualFunctions.pro file contains project configuration.

TARGET = VirtualFunctions
CONFIG   += console
TEMPLATE = app
SOURCES += main.cpp \
    abstractservice.cpp \
    userservice.cpp \
    activityservice.cpp

HEADERS += \
    abstractservice.h \
    userservice.h \
    activityservice.h

abstractservice.h is the base class that contains virtual functions.

#ifndef ABSTRACTSERVICE_H
#define ABSTRACTSERVICE_H

#include <stdio.h>

class AbstractService
{
public:
    AbstractService();
    virtual ~AbstractService();
    // calls both base and derived dest
    // prevents memory leaks

    virtual void insertRecord();
    virtual void selectRecord();
    virtual void deleteRecord();
    virtual void updateRecord();

};

#endif // ABSTRACTSERVICE_H

In the base class abstractservice.h destructor is also defined virtual otherwise derived class destructor is not called at object deletion.

abstractservice.cpp is the base class implementation file that contains implementations for virtual functions, constructor and destructor.

#include "abstractservice.h"

AbstractService::AbstractService()
{
    printf("AbstractService::AbstractService called\n");
}

AbstractService::~AbstractService()
{
    printf("AbstractService::~AbstractService called\n");
}

void AbstractService::insertRecord()
{
    printf("AbstractService::insertRecord called\n");
}

void AbstractService::selectRecord()
{
    printf("AbstractService::selectRecord called\n");
}

void AbstractService::deleteRecord()
{
    printf("AbstractService::deleteRecord called\n");
}

void AbstractService::updateRecord()
{
    printf("AbstractService::updateRecord called\n");
}

userservice.h is the first derived class that contains its own implementations for the virtual functions that are declared in the base class abstractservice.
#ifndef USERSERVICE_H
#define USERSERVICE_H

#include "abstractservice.h"

class UserService : public AbstractService
{
public:
    UserService();
    ~UserService();

    void insertRecord();
    void selectRecord();
    void deleteRecord();
    void updateRecord();
};

#endif // USERSERVICE_H

userservice.cpp contains implementation details for the base class virtual functions.
#include "userservice.h"

UserService::UserService()
{
    printf("UserService::UserService called\n");
}

UserService::~UserService()
{
    printf("UserService::~UserService called\n");
}

void UserService::insertRecord()
{
    printf("UserService::insertRecord called\n");
}

void UserService::selectRecord()
{
    printf("UserService::selectRecord called\n");
}

void UserService::deleteRecord()
{
    printf("UserService::deleteRecord called\n");
}

void UserService::updateRecord()
{
    printf("UserService::updateRecord called\n");
}

activityservice.h is the second derived class that re-declares base class virtual functions in its header.
#ifndef ACTIVITYSERVICE_H
#define ACTIVITYSERVICE_H

#include "abstractservice.h"

class ActivityService : public AbstractService
{
public:
    ActivityService();
    ~ActivityService();

    void insertRecord();
    void selectRecord();
    void deleteRecord();
    void updateRecord();
};

#endif // ACTIVITYSERVICE_H

activityservice.cpp file contains implementation details for the base class virtual functions.
#include "activityservice.h"

ActivityService::ActivityService()
{
    printf("ActivityService::ActivityService called\n");
}

ActivityService::~ActivityService()
{
    printf("ActivityService::~ActivityService called\n");
}

void ActivityService::insertRecord()
{
    printf("ActivityService::insertRecord called\n");
}

void ActivityService::selectRecord()
{
    printf("ActivityService::selectRecord called\n");
}

void ActivityService::deleteRecord()
{
    printf("ActivityService::deleteRecord called\n");
}

void ActivityService::updateRecord()
{
    printf("ActivityService::updateRecord called\n");
}

Both of the derived classes provide their own implementations for the virtual functions declared in the base class abstractservice.

main.cpp file contains a main function that is creating different base class pointers which are pointing to derived class objects.
#include "userservice.h"
#include "activityservice.h"

int main(int argc, char *argv[])
{
   UserService *userServicePtr = new UserService;
   userServicePtr->insertRecord();
   userServicePtr->selectRecord();
   userServicePtr->updateRecord();
   userServicePtr->deleteRecord();
   delete userServicePtr;
   printf("\n");

   AbstractService *abstractServiceObjPtr = new AbstractService;
   abstractServiceObjPtr->insertRecord();
   abstractServiceObjPtr->selectRecord();
   abstractServiceObjPtr->updateRecord();
   abstractServiceObjPtr->deleteRecord();
   delete abstractServiceObjPtr;
   printf("\n");

   // base class pointer to derived class object
   char option = 'a';
   AbstractService *serviceObjPtr;
   if( option == 'u' )
   {
       serviceObjPtr = new UserService;
       serviceObjPtr->insertRecord();
       serviceObjPtr->selectRecord();
       serviceObjPtr->updateRecord();
       serviceObjPtr->deleteRecord();
       delete serviceObjPtr;
       printf("\n");
   }
   else if( option == 'a' )
   {
       serviceObjPtr = new ActivityService;
       serviceObjPtr->insertRecord();
       serviceObjPtr->selectRecord();
       serviceObjPtr->updateRecord();
       serviceObjPtr->deleteRecord();
       delete serviceObjPtr;
       printf("\n");
   }

   return 0;
}

At runtime base class pointer serviceObjPtr points to either UserService instance or ActivityService instance.

Console output also shows the order for object creation and destruction.


Monday, February 10, 2014

Swap Values With Function Template

Swap values function is commonly used in applications that make operations on arithmetic values such as int,double and float. Instead of implementing overloaded functions for different data types to handle swap operation, function templates can be preferred.

Following sample project created by qt creator and contains following files:
1- UsingTemplatesInCPP.pro
2- main.cpp


UsingTemplatesInCPP.pro file contains project configuration.

TEMPLATE = app
TARGET    = UsingTemplatesInCPP
CONFIG   += console
TEMPLATE  = app
SOURCES  += main.cpp

main.cpp file contains main method and swapValues template function implementations.

#include <stdio.h>

template<typename T>
void swapValues(T &param1, T &param2)
{
    T temp = param1;
    param1 = param2;
    param2 = temp;
}

int main(int argc, char *argv[])
{

 int iP1 = 1, iP2 = 2;
 printf("Initial Integer Values : p1 = %d  p2 = %d \n", iP1, iP2);
 swapValues(iP1,iP2);
 printf("Swapped Integer Values : p1 = %d  p2 = %d \n\n", iP1, iP2);

 double dP1 = 1.34, dP2 = 2.45;
 printf("Initial Double Values : p1 = %f  p2 = %f \n", dP1, dP2);
 swapValues(dP1,dP2);
 printf("Swapped Double Values : p1 = %f  p2 = %f \n\n", dP1, dP2);

 float fP1 = 1.67, fP2 = 2.89;
 printf("Initial Float Values : p1 = %f  p2 = %f \n", fP1, fP2);
 swapValues(fP1,fP2);
 printf("Swapped Float Values : p1 = %f  p2 = %f \n", fP1, fP2);

 return 0;
}

When swapValues template function is called with integer parameters the compiler binds integer values for the generic type parameter T and instantiates an instance of the function template with integer parameters.
The same process is followed when double and float instances are instantiated.
Console output contains all the printf function results as follows :

Wednesday, February 5, 2014

Search C-String for a Specific Character

First character of a c-style string which is terminated with a '\0' char can be pointed by a char pointer , " char *ptr ". In addition to that, it is possible to use a char array, " char arr[] " for storing c-style strings. char *ptr and char arr[] can be used interchangeably.

Following sample project created by qt creator and contains following files:
1- SearchCStringForSpecificChar.pro
2- main.cpp


SearchCStringForSpecificChar.pro file contains project configuration.

TEMPLATE = app
CONFIG += console
SOURCES += main.c

main.c file contains main method which is including the algorithm that is traversing the given sample c-string "asd1 a1sd1" to search for the '1' character.
#include <stdio.h>

int main(void)
{
    const char* charArray1 = "asd1 a1sd1";
    const char* charArray2 = "asd1 a1sd1";
    printf("initial char pointer charArray1 is pointing to : %s\n", charArray1);
    printf("char pointer charArray1 is pointing to the start address of the c-string: %d \n\n", charArray1);

    int strLength = 0;
    int foundCharCount = 0;

    while(*charArray1!='\0')
    {
        printf("%c - %c - %c\n", *charArray1, charArray1[0], charArray2[strLength]);
        printf("current char pointer is pointing to the address of : %d\n\n", charArray1);

        if(*charArray1=='1')
            foundCharCount++;

        strLength++;
        charArray1++;
    }

    if(*charArray1 == '\0')
        printf("Found end of string character and exited the while loop: %d\n", *charArray1);

    printf("total number of characters : %d\n", strLength);
    printf("total number of '1' characters : %d\n", foundCharCount);
    printf("last char pointer str is pointing to :%d\n\n", *charArray1);


    return 0;
}

Both charArray1 and charArray2 pointers are containig the same const char values. Till the end-of-string character, '\0' , is found the while loop iterates in the main function.

For the current item *charArray1, charArray1[0] and charArray2[strLength] all gives the same value. If the current value is '1' then the foundCharCount variable is incremented by one.

If the current value is not '\0' then increment the strLength variable by one and move the current char pointer charArray1 to the next address location in memory for checking. Console output contains all the printf function results as follows :