searching algorithms

binary.cpp

#include <iostream>
#include <map>

/*
Time complexity: O(Log n)
*/

int searching(const int *array, int length, int value)
{
    int startIndex = 0, lastIndex = length - 1;
    int midIndex, midNumber;
    int loop_counter = 0;

    while (1)
    {
        loop_counter++;

        midIndex = startIndex + (lastIndex - startIndex) / 2;
        midNumber = array[midIndex];

        // std::cout << "startIndex: " << startIndex << " midIndex: " << midIndex << " midNumber: " << midNumber << " lastIndex: " << lastIndex << " loop_counter: " << loop_counter << std::endl;
        if (midNumber == value)
            return midIndex;

        if ((midIndex - 1) == lastIndex || (midIndex + 1) == lastIndex) // if we already reached at the end of the array
        {
            std::cout << "once called" << std::endl;
            if (array[lastIndex] == value)
                return lastIndex;

            return -1;
        }

        if (midNumber < value)
            startIndex = midIndex + 1;

        else if (midNumber > value)
            lastIndex = midIndex - 1;
    }
}

void runTest();

int main(int argc, char **argv)
{
    runTest();

    return 0;
}

void runTest()
{
    int arr[] = {0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150, 160, 170, 180};

    int index = 0;
    std::map<int, int> gquiz1;

    for (size_t i = 0; i < 250; i++)
    {
        index = searching(arr, 19, i);
        if (index > -1)
            gquiz1.insert(std::pair<int, int>(i, index));
    }

    for (auto itr = gquiz1.begin(); itr != gquiz1.end(); ++itr)
        std::cout << '\t' << itr->first << '\t' << itr->second << std::endl;
}

linear.cpp

#include <iostream>
#include <string>

using std::vector, std::cout, std::endl;

/*
Time complexity: O(N)
Auxiliary Space: O(1)

*/

int searching(const int *array, int size, int value)
{
    for (int i = 0; i < size; i++)
        if (array[i] == value)
            return i;

    return -1;
}

int main(int argc, char **argv)
{
    int arr[] = {2, 3, 4, 10, 40};

    std::cout << "Searching " << searching(arr, 5, 4) << std::endl;

    return 0;
}