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 :

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.

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 :

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 :

Traverse Array Of C-Strings Char By Char (char* array[])

char* arrayOfCStrings[] is used as an array of pointer to character. Because it is an array and each index of the array contains a pointer to the starting character of a c-string which is terminated by an end-of-string ‘\0’ character.

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

TraverseArrayOfCStringsCharByChar.pro file contains project configuration.

TARGET = TraverseArrayOfCStringsCharByChar
SOURCES += main.cpp

main.cpp file contains main method which is showing how to traverse an array of c-strings till an end-of-string character is found for each string.

#include <stdio.h>

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

    char* arrayOfCStrings[] = {"string1","string2","string3"};

    int stringCount = sizeof(arrayOfCStrings)/sizeof(char*);

    printf("Total number of strings in the string array : %d \n",stringCount);

    int i = 0;
    while(i<stringCount)
    {
        const char* currentString = arrayOfCStrings[i];
        while((*currentString))
        {
            printf(" %c ", *currentString);
            currentString++;
        }
        printf("\n");
        ++i;
    }

    return 0;
}

arrayOfStrings is initialized by curly braces.

char* arrayOfCStrings[] = {“string1”, “string2”, “string3”};

Total number of strings in the array is computed by dividing the total size of the arrayOfStrings to the size of each char* element.
int stringCount = sizeof(arrayOfCStrings)/sizeof(char*);

Outer while loop iterates till it reaches the total number c-strings. And the inner while loop iterates for each character in the current c-string till the end-of-string '\0' character is found. Console output displays the total number of c-strings in the array and each character of the current c-string in a new line.