CPT-Graphs-directed-weighted-ex1.svg

Sequential Search in C++

Okay the sequential search is easier than the recursive and iterative binary searches, I figure I would include it to wrap up searches for now. For the sequential search, you loop through an array (or whatever data structure you are using) checking each position for the search value. Works just as well on sorted array lists as it does on unsorted array lists!

Good luck, let me know if you have questions or improvements!

int sizeOfArray; //size of array, way easy to store it than calculate it everytime
int* array; //contains a list of integers that you will search through

bool sequentialFind(int number){
    for(int i = 0; i < sizeOfArray; i++){
        if (array[i] == number){
            return true;
        }
    }
    return false;
}
CPT-Graphs-directed-weighted-ex1.svg

Iterative Binary Search in C++

So yesterday’s post was on how to do a recursive binary search, today is looking at performing the exact same search on an array but doing it iteratively.  So instead of calling a function over and over and over again, we will use a loop. Again, this search is best on a sorted array.

The search function takes in an integer and will return a bool if the integer was found in a given array. The first thing we do is determine the search range, for the first loop, this will be from start of array to the end of array (0 to the size of the array),

Now we jump into the array, we will keep looping as long as the low bound is less than the high. Once the low bound is greater or equal to the high bound, we know that we exhausted the entire loop and did not find our integer in it.

Just like the recursive search, we find our middle first thing inside the loop. From there, we check if our search value is at that middle position. If not, we determine if the value is less than the middle or greater. If it is less than the middle position, we now know that the search value is in between our low bound and the middle and we can adjust our bounds for the next loop accordingly. If our value is greater than the middle, it is in between the middle and our high bound.

We keep adjusting our bounds and narrowing down the search range in this manner until the number is found or the low bound is no longer less than the high.

Happy programing, let me know if you have any questions or improvements!

int sizeOfArray; //contains the size of the search array
int* array; //integer array that we will search through

bool iterativeBinaryFind(int number){
    int highBound = sizeOfArray;
    int lowBound = 0;
    while (lowBound < highBound){
        int middle = (lowBound + highBound)/2;
        
        if (array[middle] == number) return true;
        else if (array[middle] > number) highBound = middle - 1;
        else lowBound = middle + 1;
    }
    return false;
}
CPT-Graphs-directed-weighted-ex1.svg

Recursive Binary Search in C++

I wrote a recursive binary find that looks through a sorted array for a given number.  (You can use this on an unsorted array, it just isn’t as performant.)

This is how it works, the recursive function call requires the number to search and the lowest and highest positions in a search range. To start, you give the low position, 0, and the high position, the size of the array. This is seen in the first function calling the recursive helper function. Each recursive call, first checks to make sure the low position is actually lower than the high, if it is not, the number was not found in the array. Next, we find the middle of the search section (right now it’s 0 to the size of the array). Let’s say our size is 10, so we determine the middle to be 5.

The if/else statement then works a little magic to determine if the value we have is actually in the array. First we check if the middle position contains the value we want. If it does, return true, we found our number in the array! If not, is the middle position higher than the searching value, if it is make a recursive call to our function, passing the search number, keep the low position bound and pass middle -1 as the high position bound. This is because we know the middle is higher than the search value, so the search value must be between the low and the middle positions. Else, if the two previous conditions are not true, we know the search number must be between the middle and the high position value so we pass the recursive call the search number, middle + 1 and the high value.

This process then recursively repeats itself until it either narrows down the search range and finds the search value or it cycles through and never finds the search value. Below is the code demonstrating this process. Leave comments if you have any questions or improvements.

int sizeOfArray; //size of array
int* array; //contains your array

bool recursiveBinaryFind(int searchNum){
    //pass 0 as the low pasotion and the size of the array as the highest search range position
    return recursiveBinaryFind(searchNum, 0, sizeOfArray);
}

bool recursiveBinaryFind(int searchNum, int lowBound, int highBound){
    //If the low position is greater than the high, quit we looped through everything and didn\'t find our value
    if (lowBound > highBound)    return false;
    
    //Find the middle position
    int middle = (lowBound + highBound)/2;

    //Did we find our value?
    if (array[middle] == searchNum) {
        return true;
    } else if (array[middle] > searchNum) {
        //Search the lower search range half
        return recursiveBinaryFind(searchNum, lowBound, middle - 1);
    } else {
        //Search the higher search range half
        return recursiveBinaryFind(searchNum, middle + 1, highBound);
    }
}
CPT-Graphs-directed-weighted-ex1.svg

Error: identifier “cout” is undefined

I ran across the following issue when trying to compile my AztecOO source code outside of Trilinous.

example/AztecOO/adapt_main.cpp(94): error: identifier "cout" is undefined
cout << comm << endl;
^
example/AztecOO/adapt_main.cpp(94): error: identifier "endl" is undefined
cout << comm << endl;
^
example/AztecOO/adapt_main.cpp(96): error: identifier "cerr" is undefined
if(argc != 2) cerr << "error: enter name of data file on command line" << endl;

Fix
The compiler doesn’t recognize that these methods come from the standard library. Therefore, I must tell it with the following commands:

using std::cout;
using std::endl;
using std::cerr;

Credit goes to http://stackoverflow.com/questions/13208547/the-includeiostream-exists-but-i-get-an-error-identifier-cout-is-undefine.

CPT-Graphs-directed-weighted-ex1.svg

AztecOO catastrophic error: cannot open source file “Epetra_Map.h”

A while back I was trying to compile the AztecOO library outside of Trilinous. See this early post for more details. In doing so, I received the following error:

catastrophic error: cannot open source file "Epetra_Map.h"

Solution
Aztec requires quite a few of the additional tilinous header files. I copied a couple addition src directories from trilinous to my Aztec src folder. The list below shows everything I copied into source. I recommend you keep your AztecOO src directory organized and make folders for the external libraries. Also make sure to have correctly included directories with –I in the compile statement to ensure that the compiler looks into the Aztec src directory for the correct files.

Directories I copied:
trilinos-11.10.1-Source/packages/epetra/src
trilinos-11.10.1-Source/packages/teuchos/core/src
trilinos-11.10.1-Source/packages/teuchos/comm/src
trilinos-11.10.1-Source/packages/teuchos/parameterlist /src
trilinos-11.10.1-Source/packages/epetraext/src

Files
trilinos-11.10.1-Source/packages/triutils/src/Trilinos_Util.h
trilinos-11.10.1-Source/packages/triutils/src/Trilinos_Util_ReadMatrixMarket2Epetra.h
trilinos-11.10.1-Source/packages/epetraext/src/inout/EpetraExt_OperatorOut.h
trilinos-11.10.1-Source/packages/epetraext/src/EpetraExt_ConfigDefs.h

I also copied the additional files from the build version of trilinous (these files are generated upon ‘make’ in Trilinous).

trilinos.build/packages/epetra/src/Epetra_config.h
trilinos.build/packages/epetra/src/Epetra_DLLExportMacro.h
trilinos.build>/packages/teuchos/core/src/Teuchos_config.h
trilinos.build/Trilinos_version.h
trilinos.build/packages/triutils/src/Triutils_config.h
trilinos.build/packages/teuchos/core/src/Teuchos_config.h

I also had to remove some directories
aztecoo/example

CPT-Graphs-directed-weighted-ex1.svg

Catastrophic error: cannot open source file

A while back I was trying to compile the AztecOO library outside of Trilinous. See this early post for more details. In doing so, I received the following error:

catastrophic error: cannot open source file "az_aztec.h"

Solution
This was a simple oversight on my part. To fix this, I added –I./src to the compile statement to make sure it looked in the Aztec src directory for header files, etc. Same goes for anyone experiencing a similar error.

CPT-Graphs-directed-weighted-ex1.svg

AztecOO: error: identifier “sswap_” is undefined

Error
I’ve been trying to compile the AztecOO library outside of Trilinous. In doing so, I pulled the package Aztec source code from the Trilinous source code and opted to write my own Makefile to then compile it. My Makefile included the same settings reported in the Trilinous Makefile.export.AztecOO file.

To prepare this build, I needed to fetch the AztecOO_config.h file from a built version of Trilinous and place it in the source directory of the Aztec directory I was compiling (this file is generated upon ‘make’ in Trilinous). With that in place, I had the files I needed to compile Aztec, however, I ran into the following error.

error: identifier "sswap_" is undefined

Solution
SWAP_F77 is a defined module that points to the F77_BLAS_MANGLE module at the top of az_c_util.c. This second module is defined in AztecOO_config.h. All this module does, is add a “_” to the end of the name provided in the parameters and defines it with the provided value. This works when you are using the Fortran Blas library, but I am using the C version. To fix this, I edited all F77 functions in the AztecOO_config.h file to just return “name” instead of “name ## _”.

I also added this include statement to the file that errors src/az_c_util.c which required that I add –I to the compile statement in order for the compiler to find the right header files.

#include "mkl_blas.h"