Dynamic array of Linear search funcion implementation

user_409821 0
Viewed 121

Need to implement a function

int* linearSearch(int* array, int num);

That gets a fixed size array of integers with a number and return an array with indices to the occurrences of the searched number. For example array={3,4,5,3,6,8,7,8,3,5} & num=5 will return occArray={2,9}. I've implemented it in c++ with a main function to check the output

#include <iostream>
using namespace std;
int* linearSearch(int* array, int num);

int main()
{
    int array[] = {3,4,5,3,6,8,7,8,3,5}, num=5;
    int* occArray = linearSearch(array, num);
    int i = sizeof(occArray)/sizeof(occArray[0]);
    while (i>0) {
        std::cout<<occArray[i]<<" ";
        i--;
    }
}

int* linearSearch(int* array, int num)
{
    int *occArray= new int[];
    for (int i = 0,j = 0; i < sizeof(array) / sizeof(array[0]); i++) {
        if (array[i] == num) {
            occArray[j] = i;
            j++;
        }
    }
    return occArray;
}

I think the logic is fine but I have a syntax problems with creating a dynamic cell for occArray Also a neater implantation with std::vector will be welcomed

Thank You

dynamic-arrays linear-search stdvector c++
1 Answers

At very first I join in the std::vector recommendation in the question's comments (pass it as const reference to avoid unnecessary copy!), that solves all of your issues:

std::vector<size_t> linearSearch(std::vector<int> const& array, int value)
{
    std::vector<size_t> occurrences;
    // to prevent unnecessary re-allocations, which are expensive,
    // one should reserve sufficient space in advance
    occurrences.reserve(array.size());
    // if you expect only few occurrences you might reserve a bit less,
    // maybe half or quarter of array's size, then in general you use
    // less memory but in few cases you still re-allocate

    for(auto i = array.begin(); i != array.end(); ++i)
    {
        if(*i == value)
        {
            // as using iterators, need to calculate the distance:
            occurrences.push_back(i - array.begin());
        }
    }
    return occurences;
}

Alternatively you could iterate with a size_t i variable from 0 to array.size(), compare array[i] == value and push_back(i); – that's equivalent, so select whichever you like better...

If you cannot use std::vector for whatever reason you need to be aware of a few issues:

You indeed can get the length of an array by sizeof(array)/sizeof(*array) – but that only works as long as you have direct access to that array. In most other cases (including passing them to functions) arrays decay to pointers and these do not retain any size information, thus this trick won't work any more, you'd always get sizeOfPointer/sizeOfUnderlyingType, on typical modern 64-bit hardware that would be 8/4 = 2 for int* – no matter how long the array originally was.

So you need to pass the size of the array in an additional parameter, e.g.:

size_t* linearSearch
(
    int* array,
    size_t number, // of elements in the array
    int value      // to search for
);

Similarly you need to return the number of occurrences of the searched value by some means. There are several options for:

  1. Turn num into a reference (size_t& num), then you can modify it inside the function and the change gets visible outside. Usage of the function get's a bit inconvenient, though, as you need to explicitly define a variable for:
size_t num = sizeof(array)/sizeof(*array);
auto occurrences = linearSearch(array, num, 7);
  1. Append a sentinel value to the array, which might be the array size or probably better maximum value for size_t – with all the disadvantages you have with C strings as well (mainly having to iterate over the result array to detect the number of occurences).
  2. Prepend the number of occurrences to the array – somehow ugly as well as you mix different kind of information into one and the same array.
  3. Return result pointer and size in a custom struct of yours or in e.g. a std::pair<size_t, size_t*>. You could even use that in a structured binding expression when calling the function:
auto [num, occurences] = linearSearch(array, sizeof(array)/sizeof(*array), 7);
//                                           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
// here the trick yet works provided the array is declared above the call, too,
// as is in your example

Option 4 would be my personal recommendation out of these.

Side note: I switched to size_t for return values as negative indices into an array are meaningless anyway (unless you intend to use these as sentinel values, e. g. -1 for end of occurrences in option 2).

user_13123820
Related