Recursion and Finding the Index of an Element

[jhykima]

I know I have been posting so often and I apologize. I am learning so much and I have so many questions!

I am trying to write a program that takes a sorted array and a target element and finds the element in the array and return the index of the array. I was able to write a program that takes four arguments accomplishes this objective.

However, I want to write a program that only takes in two arguments, namely, the array and the target element that returns the index of the target element. Any suggestions on how to accomplish this?

#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std; 

void findIndexOfArray (int *array, int userInput, int start, int end)
{
	if (start < end)
	{
		if (*array != userInput)
		{
			findIndexOfArray (array + 1, userInput, start + 1, end);	 
		}
		else
		{
			cout << "The index of the element is " << start << endl;
		}
	}
}

int main() 
{
	int userInput; 
	int array[10]; 
	int start = 0;
	int end = 10;  
	for (int i = 0; i < 10; i++)
	{
		array[i] = 5 + i;
		cout << array [i] << endl;
	}

	cout << endl;

	cin >> userInput; 
	while (userInput > 0)
	{
		findIndexOfArray (array, userInput, start, end); 
		cin >> userInput; 
	}
	return 0; 
}

[keskiverto]

Why? Why recursion and why only two arguments?

[jhykima]

@keskiverto

HAHAHA. Because the book that I am studying off of is asking me to!!! I have no idea why!!! I'm guessing its good practice? Is it possible?!!!

[keskiverto]

rose by any other name would smell as sweet

That is to say that an array is not a single number. It must have both starting address and number of elements. The function has to receive the data somehow.

One could play trickery and hide some/all info in global variables, but that is a poor, restrictive workaround that merely reduces the number formal function parameters.

The "best" way might be the use of standard library containers, like std::vector. One argument encapsulates all data about the array. The standard library algorithms, however, do not take one container parameter; they expect a pair of "iterators" to the container.


No matter what you do, you do need more than two arguments.


Your current recursion is very close to a iterative loop. Such recursion does not gain you anything.

More importantly, it does not make use of a crucial property of the input data:

takes a sorted array

What if the searched value is in the last element (or not at all in the array)? Your algorithm has to compare every element in the array in order to find that out.

If the input is already sorted, then the recursion can implement a much smarter search strategy.


PS. IMHO the function should return a value and not print anything. Let the caller (main) can use the value as it likes. Of course, the function should then be able to return an index that means that there is no element with the searched value ...

[jhykima]

@keskiverto

Thank you for your response.

I remember in our past conversation, you mentioned that I should learn vectors. I have not gone around it to learning it yet. But I will soon... in like two more chapters.

What does IMHO mean?

Okay. I will try to find the smarter search strategy and will get back to you.

Best regards,
Jae Kim

[jhykima]

@keskiverto

I am thinking maybe dividing the array in half? And so now the function only has to check half of the array instead of the whole list? Is the startegy something like this?

[keskiverto]

Yes. You have a (ascending) sorted array. If you do select an element -- lets call it "pivot" -- then there are three possibilities:

1. The searched value is less than the value of the pivot. In that case the searched value could be somewhere before the pivot.

2. The searched value is greater than the value of the pivot. In that case the searched value could be somewhere after the pivot.

3. The value of the pivot equals the searched value and you have found an element that you are seeking.


In the first two cases you do have a shorter array to search from and can recurse. If the (sub)array has no elements, then the whole array does not contain the value that you are searching.

[andywestken]

I am curious about the challenge to find a solution with just two parameters. I can see ways to fudge the issue, but if you're talking about a C array and built-in type parameters then, as keskiverto has said, there's no way to do it with less than three arguments.

What book are you talking about?

Andy

[S G H]

IMHO = In My Honest (Humble) Opinion

@Two arguments: It is possible for you to use only two arguments (with some tricky template help) but:
1. it's going to SEVERELY limit the algorithm (namely, you are forced to search in the *entire* array).
2. You can only traverse it (e.g. no taking shortcuts)).
3. You internally still end up using three arguments (two are regular arguments and one is a template argument).

This would do it:

#include <iostream>

template <typename T, unsigned int N>
struct search_item_helper {
    static T* search_item_ct_size(T* array, T const& item) {
        if(*array == item)
            return array;
        return search_item_helper<T,N-1>::search_item_ct_size(array+1,item);
    }
};

template <typename T>
struct search_item_helper<T,0> {
    static T* search_item_ct_size(T*,T const&){return 0;}
};

template <typename T, unsigned int N>
T* search_item(T (&array)[N], T const& item)
{
    if(*array == item)
        return array;
    return search_item_helper<T,N-1>::search_item_ct_size(array+1,item);
}

int main(int,char**)
{
    int array[] = {0,1,2,3,5};
    int* item_two = search_item(array,2);
    int* item_four = search_item(array,4);
    
    std::cout << "Item 2 has " << (item_two ? "" : "not ") << "been found." << std::endl;
    std::cout << "Item 4 has " << (item_four ? "" : "not ") << "been found." << std::endl;
    
    if(item_two)
        std::cout << "Item 2: " << *item_two << std::endl;
    if(item_four)
        std::cout << "Item 4: " << *item_four << std::endl;
    return 0;
}

Item 2 has been found.
Item 4 has not been found.
Item 2: 2

EDIT: Actually you can use a starting pivot and take shortcuts. Feel free to play with the above code if you feel like doing so.

[jhykima]

@andywestken

Yea... I had no idea how to do it. And maybe the book just forgot to mention it or something, that I can use more than two parameters for the function. The book that I am currently studying off of is called Jumping Into C++ by Alex Allain.

@S G H

Thank you so much for your response. I'm still a huge noob and there's a lot of syntax there I do not understand yet. Perhaps, in the future, I will take a look at it and it will make sense. Regardless, thank you so much for writing that to help me! I appreciate it.

@keskiverto

Got it. Let me write that code right now, if you can look it over, that would be awesome.

[jhykima]

@keskiverto

The following probably proves what a noob I am. I honestly don't think it's anymore efficient than checking each element... but here it is... Let me know what you think.

int find_index (int cnt, int pivot, int num_elements, int input, int *array)
{
	if (input > array[pivot])
	{
		if (array[cnt] == input)
		{
			return cnt; 
		}
		else if (input > array[num_elements])
		{
			return -1; 
		}
		find_index(cnt + 1, pivot, num_elements, input, array); 
	}
	else if (input < array[pivot])
	{
		if (array[cnt] == input)
		{
			return cnt;
		}
		else if (input < array[0])
		{
			return -1; 
		}
		find_index(cnt - 1, pivot, num_elements, input, array); 
	}
	else 
	{
		return pivot; 
	}
}

int main() 
{	
		int index; 
		int num_elements; 
		cin >> num_elements; 
		int array[num_elements]; 
		int pivot = num_elements / 2; 
		int cnt = pivot; 
		cout << endl;

		for (int i = 0; i < num_elements; i++)
		{
			array[i] = i + 5; 
			cout << array[i] << endl;
		}

		num_elements = num_elements	- 1; 
		cout << endl;
		int input;  
		cin >> input; 
		while (input)
		{
			index = find_index (cnt, pivot, num_elements, input, array); 
			cout << "The index is: " << index << endl;
			cin >> input; 
		}
	return 0;
}

[keskiverto]

Lines 13 and 25 do call a function, but do not do anything with the value that the function returns.
Line 38 is not supported by the standard; the size of an array must be known already during compilation.
Line 1: the function does not modify the array, so the array should be const.
Line 56: what if index is -1?


Consider this:

// find value input from range [begin..end[ within array
// return index, or -1 if value is not found
// range must be sorted to ascending order
int find( const int * array, int begin, int end, int input );

[andywestken]

The requirement to use two parameters isn't there.

From Chapter 16: Recursion of Jumping Into C++ by Alex Allain

Practice problems

4. Write a recursive function that takes a sorted array and a target element and finds that element in the array (returning the index, or -1 if the element isn’t in the array). How fast can you make this search? Can you do better than having to look at every element?

and earlier in the book, Chapter 10: Arrays, section Passing arrays to functions

Of course, unless the function knows how big the array is, to use the array, that function needs to take the size of the array as a second parameter:

int sumArray (int values[], int size)

This is just after explaining that array size information is lost when calling functions. And later in the Arrays chapter he gives a (non-recursive) sort example that takes an array which take two parameters

void sort (int array[], int size)

So it's all as I would have expected! He doesn't say that you've got to pass the array using a single parameter.

Andy

PS If you add the required #includes to your code then people will be able to use the little 'cog wheel' button to run it on the C++ Shell website.

[andywestken]

Given the use a non-const array size I think you must be using the GCC compiler. (This is a feature from C99 rather than C++)

Also, it appears that your find_index() function is only working when you are (a) not returning from all control paths in the function. or (b) even explicity handling the return code from your recursive calls. The compiler has clearly decided to return the return from the recurvive calls automatically for you.

(I have checked and this happens with the Visual C++ compiler, too.)

It would better to write the following for line 13

return find_index(cnt + 1, pivot, num_elements, input, array);

(and similarly for line 25), which is what the compiler is doing anyway.

Andy

PS It might help to up the warning level your compiler is using, and get it to treat non-standard usage as an error, by adding -Wall -Wextra -pedantic-errors to your C++ Compiler Options.

(when working with pure C++ with the Visual C++ compiler I would up the warning level to /Wall and Disable Language extensions (/Za), but with Windows code you need the language extensions and /W4.)

[keskiverto]

I just realized that my function signature is very similar to the practically iterative function in the OP.

Lets more or less take that and add a benchmark around it.

#include <iostream>
#include <chrono>
#include <numeric>
#include <random>

size_t tests = 0;

// find value input from range [begin..end[ within array
// return index, or -1 if value is not found
int find( const int * array, int begin, int end, int input ) {
  if ( begin < end ) {
    ++tests;
    if ( array[begin] == input ) {
      return begin;
    }
    else {
      return find( array, begin+1, end, input );
    }
  }
  else {
    return -1;
  }
}

int main() {
  using namespace std::chrono;

  constexpr int N =  10000;
  int arr[N];
  std::iota( arr, arr+N, 42 ); // arr has values [42..10041]

  unsigned seed = system_clock::now().time_since_epoch().count();
  std::default_random_engine generator( seed );
  std::uniform_int_distribution<int> distribution( 0, N+200 );
  constexpr int T = 100000;
  int key[T];
  for ( auto & x : key ) {
    x = distribution(generator); // key has T random values, all [0..100200]
  }

  tests = 0;
  std::cout << "searching " << T << " times...\n";
  int count = 0;
  high_resolution_clock::time_point t1 = high_resolution_clock::now();
  for ( int i = 0; i < T; ++i ) {
    int hit = find( arr, 0, N, key[i] );
    if ( -1 != hit ) {
      //std::cout << key << " is at " << hit << '\n';
      ++count;
    }
  }
  high_resolution_clock::time_point t2 = high_resolution_clock::now();
  duration<double> time_span = duration_cast<duration<double>>(t2 - t1);
  std::cout << std::fixed << "It took me " << time_span.count()
    << " seconds and found value " << count << " times.\n";
  std::cout << "On average " << static_cast<double>(tests)/T
    << " element comparisons per search.\n";
  
  return 0;
}

This program does on average 5100 comparisons per search.

If the find() is changed to use the recursive strategy that I described earlier, then the comparisons per search (and time) drops a lot. How much?

[jhykima]

@keskiverto

Lines 13 and 25 do call a function, but do not do anything with the value that the function returns.

Must I do something with the value that is returned? Well, in my main, aren't I technically couting the returned value and thereby doing something with it?

Line 1: the function does not modify the array, so the array should be const.

Why is it necessary to do so?

I'm sorry. Your code is waaaaaaay beyond what I can understand. I feel super bad because you took the time to write that beautiful piece of code but I can't even understand it.

Also, what do you earn a living?

@andywestken

Thank you for the clarification. Do you have the book?

Also, how do up the warning level? I am currently using cygwin but I'm not sure how to change the warning level on it...

[andywestken]

Cygwin isn't the compiler. Usually you use the GCC compiler (g++) with Cygwin.

Are you using g++ directly?, via a makefile? or are you using an IDE (Code::Blocks, CodeLite, ... ?)??

The switches I suggested need to be passed to the compiler.

I don't have a copy of the book, but as I was curious about how the problem statement was phrased I snuck a look at a copy I found online.

Andy

[andywestken]

"Backport..."

Andy

#include <iostream>
#include <iomanip>
#include <numeric>
//#include <random> EDIT <random> is for new random functions
#include <cstdlib> // but old ones live here!
#include <ctime>
using namespace std;

int g_test_count = 0;

// find value input from range [beg..end] within arr
// return index, or -1 if val is not found
int find(const int* arr, int beg, int end, int val) {
    if (beg < end ){
        ++g_test_count;
        if (arr[beg] == val) {
            return beg;
        } else {
            return find(arr, beg + 1, end, val);
        }
    } else {
        return -1;
    }
}
int main() {
#ifdef _DEBUG
    // when built with MSVC unoptimized (debug build) the
    // stack blows for an array size of 7200 odd. Plus it
    // is really slow. But release build is ok.
    const int arr_size  =   2500;
#else
    const int arr_size  =  10000;
#endif
    const int val_count = 100000;

    srand(123); // fixed seed for test repeatability

    int arr[arr_size];
    for (int i = 0; i < arr_size; ++i)
        arr[i] = (i + 42); // arr of values in range [42..10041]

    int val[val_count];
    for (int i = 0; i < val_count; ++i)
        val[i] = rand() % (arr_size + 200); // random values in range [0..10199]

    g_test_count = 0;

    int found_count = 0;

    cout << "searching " << val_count << " times...\n";

    clock_t ticks_begin = clock();

    for (int i = 0; i < val_count; ++i) {
        int idx = find(arr, 0, arr_size, val[i]);
        if (-1 != idx) {
            //cout << val << " is at " << idx << '\n';
            ++found_count;
        }
    }

    clock_t ticks_end = clock();

    double secs_taken = static_cast<double>(ticks_end - ticks_begin)
                      / static_cast<double>(CLOCKS_PER_SEC);
    double elems_avg  = static_cast<double>(g_test_count)
                      / static_cast<double>(val_count);

    cout << fixed << setprecision(2)
         << "It took me " << secs_taken << " seconds\n"
         << "and found value " << found_count << " times.\n"
         << "On average " << elems_avg << " element comparisons per search.\n";

    return 0;
}

[jhykima]

@andywestken

Yes, I think I am using it directly because every time I want to compile, I write g++ file.cpp and to execute I write ./file.exe.

Also, I think the code that you wrote might be a little bit more understandable. I know most of the syntax so thank you so much for posting that.

Also, I tried running your code and I got the following error message:

In file included from /usr/lib/gcc/x86_64-pc-cygwin/4.9.2/include/c++/random:35:0,
from a.cpp:4:
/usr/lib/gcc/x86_64-pc-cygwin/4.9.2/include/c++/bits/c++0x_warning.h:32:2: error: #error This file requires compiler and library support for the ISO C++ 2011 standard. This support is currently experimental, and must be enabled with the -std=c++11 or -std=gnu++11 compiler options.
#error This file requires compiler and library support for the \
^
a.cpp: In function ‘int main()’:
a.cpp:35:14: error: ‘srand’ was not declared in this scope
srand(123); // fixed seed for test repeatability
^
a.cpp:43:23: error: ‘rand’ was not declared in this scope
val[i] = rand() % (arr_size + 200); // random values in range [0..10199]
^

Just wondering, why do you take the time to answer your questions? It really doesn't benefit you at all. I hope this question doesn't come off as rude.

Further, is the following code okay? As in is it standard usage?

	int board_size; 
	cin >> board_size; 
	string **p_p_omok_board; 
	p_p_omok_board = new string*[board_size]

[andywestken]

error: #error This file requires compiler and library support for the ISO C++ 2011 standard

To fix this you need to use

g++ -std=c++11 file.cpp

to build your exe.

(It would be better to use a script, batch file, or makefile, then you can add -Wall -Wextra -pedantic-errors as well. A bit too much to type in each time.

error: ‘srand’ was not declared in this scope

Sorry - my mistake. Replace

#include <random>

with

#include <cstdlib>

(<random> is for the new random functions.)

Further, is the following code okay? As in is it standard usage?

	int board_size; 
	cin >> board_size; 
	string **p_p_omok_board; 
	p_p_omok_board = new string*[board_size]

Not sure.

If it's an array of std::string I would expect just

string *p_omok_board = new string[board_size]

as there's no need so allocate the individual strings using new.

And what I would expect to see (i.e. what is standard usage) is

vector<string> omok_board(board_size);

Andy

PS regarding...

Just wondering, why do you take the time to answer your questions? It really doesn't benefit you at all. I hope this question doesn't come off as rude.

It does benefit me, By explaining how things work it helps me review my own skills. Some questions on cplusplus.com definitely make me think about C++ in a way which doesn't happen at work where things can sometimes get a bit routine (from a C++ point of view, rather then software engineering.).

It also helps me to improve my communication skills. How to explain a solution at the right level. And clearly, succinctly, and completely. I am also trying to avoid spoon feeding, though that can be hard sometimes.