Counting the number of comparisons in an array to find a value

  • (2 Pages)
  • +
  • 1
  • 2

15 Replies - 978 Views - Last Post: 07 June 2011 - 04:17 PM Rate Topic: -----

#1 Mideoan  Icon User is offline

  • D.I.C Head

Reputation: 4
  • View blog
  • Posts: 77
  • Joined: 31-May 11

Counting the number of comparisons in an array to find a value

Posted 06 June 2011 - 04:23 PM

I'm having some difficulty figuring out how to loop a counter in an array to determine how many elements my function must go through before it finds a value. For example, I have a linear search algorithm and a binary search algorithm. Each has a different method of searching about the array and each will more than likely have a different outcome value in at the end of how many counts it took to get there. I understand how a loop counter works, but I'm clueless as to get it to access the array.

I tried something like this
while (resultsBinary < SIZE)
	 count++;
	cout << count << endl;


but it only counts in a sequential order for both.

Here is my full code without the above code.



#include <iostream>
using namespace std;

//Function prototype
int searchList(int [], int, int);
int binarySearch(int [], int, int);
const int SIZE = 20;

int main()
{
	int numbers[SIZE] = {12, 13, 14, 15, 17, 21, 24, 25, 26, 29,
						 31, 36, 37, 38, 39, 45, 52, 75, 91, 95};
	
	int resultsLinear;
	int resultsBinary;
	int numberHold;
	int count = 0;

	// Search for a number
	cout << "Enter a number you wish to search the array for: ";
	cin >> numberHold;
	{
	resultsLinear = searchList(numbers, SIZE, numberHold);

	
	if (resultsLinear == -1)
		cout << "The number you entered was not found." << endl;
	else 
	{
		cout << " Your number, " << numberHold << " was in array field " << resultsLinear << ". " << endl;
	}
	
	
	}

	
	{
	resultsBinary = binarySearch(numbers, SIZE, numberHold);

	

	if (resultsBinary == -1)
		cout << "That number does not exist in this array. " << endl;
	else
	{
		cout << " That number is " << resultsBinary << " in the array." << endl;
	}
	system("Pause");
	return 0;

}
	system("Pause");
	return 0;
}

	





// Linear Search Algorithm
int searchList (int list[], int numElems, int value)
{
	int index = 0;
	int position = -1;
	bool found = false;

	while (index < numElems && !found)
	{
		if (list[index] == value)
		{
			found = true;
			position = index;
		}
		index++;
	}
	return position;
}


// Binary Search Algorithm
int binarySearch(int array[], int numElems, int value)
{
	int first = 0,
		last = numElems - 1,
		middle,
		position = -1;
	bool found = false;

	while (!found && first <= last)
	{
		middle = (first + last) / 2;
		if (array[middle] == value)
		{
			found = true;
			position = middle;
		}
		else if (array[middle] > value)
			last = middle - 1;
		else first = middle + 1;
	}
	return position;
}



Is This A Good Question/Topic? 0
  • +

Replies To: Counting the number of comparisons in an array to find a value

#2 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: Counting the number of comparisons in an array to find a value

Posted 06 June 2011 - 04:30 PM

This may be one of those places where the comma operator is handy.

The comma operator lets you evaluate multiple sub-expressions and then the overall comma-expression takes the value of the last evaluated expression:

int result = (<expression1>, <expression2>, <expression3>) + 1;

This line will first evaluate expression1, then evaluate expression2 and then evaluate expression3 then add one to that value and assign that to result. So result = expression3 + 1


So you can go: while((count++, list[index] != value)) { index++; }

granted here you could easily have put the count++ into the inner part of the loop but there are other places where it is a little more convent. and you can ensure that it gets added at each place a comparison happens.
Was This Post Helpful? 1
  • +
  • -

#3 Mideoan  Icon User is offline

  • D.I.C Head

Reputation: 4
  • View blog
  • Posts: 77
  • Joined: 31-May 11

Re: Counting the number of comparisons in an array to find a value

Posted 06 June 2011 - 05:09 PM

I do appreciate your help, but I guess I should start with saying that I'm pretty new to C++ and have only experienced two other languages (Java and VB) of which I'm still pretty new at as well. If it's not to much trouble, could you break down what you said into more "noob" terms? I understand
while((count++, list[index] != value)) { index++; }

but just don't understand it completely as variables list, value, and index are shown in the function but the count is listed in my main code.
Was This Post Helpful? 0
  • +
  • -

#4 and1dre  Icon User is offline

  • D.I.C Head

Reputation: 5
  • View blog
  • Posts: 69
  • Joined: 30-March 09

Re: Counting the number of comparisons in an array to find a value

Posted 06 June 2011 - 06:20 PM

For the linear you can just do a while loop that checks if the number entered does not equal to the number your looking for in the array. If it doesn't equal, increment a counter.

For example,

int count = 0;
int i = 0;
while(numberEntered != array[i]){
//increment count
//increment i to check next position in array
}

return count; //total number of looks in the array




Hope this helps a little.
Was This Post Helpful? 0
  • +
  • -

#5 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: Counting the number of comparisons in an array to find a value

Posted 06 June 2011 - 07:09 PM

Ok well this seems to then stem into the area of functions in C/C++. There are a couple of different ways to get data into and back from a function.

Generally to get data into a function you pass the data in via and argument. You can do this in two ways (although it seems like three in C++) -- you can pass by value or pass by reference.

pass by value makes a copy of the data and hands it to the function. -- since the function only has a copy of the data all changes made by the function are lost when it exits.

Pass by reference gives the function a pointer or reference to the data -- since the function can now access the data directly any chances made by the function persist past the function returning. - so pass by reference is not only a way to get data into a function, it is a way to get data back from a function!

The other way to get data back from a function is to "return" it -- return has a few shortcomings, for example you can only return 1 "value" (better to think of this as 1 variable).

The other, and generally frowned upon, way to get data into and back from a function is a terrible thing called a "global variable" -- since I disapprove of this approach I will skip its description.

So if you wanted to get the count back from
int binarySearch(int [], int, int);

you could change that to:
int binarySearch(int [], int, int, int&);

then make the function:
int binarySearch(int array[], int numElems, int value, int& count)
Was This Post Helpful? 2
  • +
  • -

#6 Mideoan  Icon User is offline

  • D.I.C Head

Reputation: 4
  • View blog
  • Posts: 77
  • Joined: 31-May 11

Re: Counting the number of comparisons in an array to find a value

Posted 06 June 2011 - 07:48 PM

Still pretty lost with all this. I thought I understood, but apparently not and it's frustrating me beyond belief! I added a 4th comma operator, but now I'm getting issues when I execute because my while statement isn't placed correctly in the functions. This may be one section that I just won't understand. Code as it sits now. . .




#include <iostream>
using namespace std;

//Function prototype
int searchList(int [], int, int, int);
int binarySearch(int [], int, int, int);
const int SIZE = 20;

int main()
{
	int numbers[SIZE] = {12, 13, 14, 15, 17, 21, 24, 25, 26, 29,
						 31, 36, 37, 38, 39, 45, 52, 75, 91, 95};
	
	int resultsLinear;
	int resultsBinary;
	int numberHold;
	int count = 0;
	int i = 0;

	// Search for a number
	cout << "Enter a number you wish to search the array for: ";
	cin >> numberHold;
	{
	resultsLinear = searchList(numbers, SIZE, numberHold, count);

	
	
	
	if (resultsLinear == -1)
		cout << "The number you entered was not found." << endl;
	else 
	{
		cout << " Your number, " << numberHold << " was in array field " << resultsLinear << " and counted as number " 
			<< count << " in the linear function. " << endl;
	}
	
	
	}

	
	{
	resultsBinary = binarySearch(numbers, SIZE, numberHold, count);


	if (resultsBinary == -1)
		cout << "That number does not exist in this array. " << endl;
	else
	{
		cout << " That number is " << resultsBinary << count << " in the array." << endl;
	}
	system("Pause");
	return 0;

}
	system("Pause");
	return 0;
}

	





// Linear Search Algorithm
int searchList (int list[], int numElems, int value, int linamount)
{
	int count = 0;
	int index = 0;
	int position = -1;
	bool found = false;

	while((count++, list[index] != value)) { index++; }

	while (index < numElems && !found)
	{
		if (list[index] == value)
		{
			found = true;
			position = index;
		}
		index++;
	}
	 
	

	return position;
	return count;

	
}


// Binary Search Algorithm
int binarySearch(int array[], int numElems, int value, int binamount)
{
	int count = 0;
	int index = 0;
	int first = 0,
		last = numElems - 1,
		middle,
		position = -1;
	bool found = false;

	while((count++, middle != value)) { index++; }

	while (!found && first <= last)
	{
		middle = (first + last) / 2;
		if (array[middle] == value)
		{
			found = true;
			position = middle;
		}
		else if (array[middle] > value)
			last = middle - 1;
		else first = middle + 1;
		 
	}
	
	
	return position;
	return count;
}


Was This Post Helpful? 0
  • +
  • -

#7 Oler1s  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1395
  • View blog
  • Posts: 3,884
  • Joined: 04-June 09

Re: Counting the number of comparisons in an array to find a value

Posted 06 June 2011 - 08:11 PM

Translate your searchList code to English. I don't mean what you want the function to do. I mean go line by line and give me an English version of that line.
Was This Post Helpful? 0
  • +
  • -

#8 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: Counting the number of comparisons in an array to find a value

Posted 06 June 2011 - 10:20 PM

...you do realize that you can't just copy and paste my example above into your code and have it necessarily work. I mean I didn't really put all that much thought into making sure that my exact example was directly compatible with your logic.

I wrote the line:
while((count++, list[index] != value)) { index++; }

to demonstrate how to insert the comma operator into places where you do a compairison. But what does that do... lets assume that list was: {1, 2, 3, 4, 5} and we were looking for 4

well, first count gets incremented: count = 1
then we do the comparison 1 != 4 which is a true statement
so the inner part of the while executes index++ so index = 1
Then count++: count = 2
compare 2 != 4 which is true
index++ : index = 2
count++: count = 3
compare 3 != 4 which is true
index++: index = 3
count++: count = 4
compare 4 != 4 which is false!!!
we DO NOT execute the inner part of the loop.

ok so that work for a this case of a linear search. What if we wanted to look for 28?
Well here we have a problem, running though the same routine as before but comparing with the value of 28 we get all the way to:

compare 5 != 28 which is true,
index++: index = 5
count++
compare ??? != 28.... list[5] is undefined so now we have a problem!!!

So, my code was not a proper search it was just an example on how to use the comma operator in your code.

So... erase my line and lets look at your original function:

// Linear Search Algorithm
int searchList (int list[], int numElems, int value) {
    int index = 0;
    int position = -1;
    bool found = false;

    while (index < numElems && !found) {
        if (list[index] == value) {
            found = true;
            position = index;
        }

        index++;
    }

    return position;
}


now we want to add a count++ to the part(s?) where there is a comparison. So there are actually 3 (arguably 4) comparisons... but lets just count the ones where list[index] is compared to our value.

so we add the comma operator into the place where the comparison we are interested in takes places.

// Linear Search Algorithm
int searchList (int list[], int numElems, int value) {
    int index = 0;
    int count = 0;
    int position = -1;
    bool found = false;

    while (index < numElems && !found) {
        if ((count++, list[index] == value)) {
            found = true;
            position = index;
        }

        index++;
    }

    return position;
}


now we can't return it as we can only return 1 variable... so we have to use either:

1) pass by reference
2) a global variable.

I suggest #1
Was This Post Helpful? 2
  • +
  • -

#9 Mideoan  Icon User is offline

  • D.I.C Head

Reputation: 4
  • View blog
  • Posts: 77
  • Joined: 31-May 11

Re: Counting the number of comparisons in an array to find a value

Posted 07 June 2011 - 12:26 PM

Perfect. That cleared up the mud in the water quite a bit for me. I understand now how the comma operator is used to make the count++ tally it up. My only issue now is understanding how to use pass by reference to call the count value from the function since I am already returning the position variable and you say that global variables are not recommended. Here is my fixed functions for both linear and binary.

// Linear Search Algorithm
int searchList (int list[], int numElems, int value)
{
	int count = 0;
	int index = 0;
	int position = -1;
	bool found = false;

	

	while (index < numElems && !found)
	{
		if ((count++, list[index] == value))
		{
			found = true;
			position = index;
		}
		index++;
	}
	 
	

	return position;
	

	
}


// Binary Search Algorithm
int binarySearch(int array[], int numElems, int value)
{
	int count = 0;
	int index = 0;
	int first = 0,
		last = numElems - 1,
		middle,
		position = -1;
	bool found = false;

	

	while (!found && first <= last)
	{
		middle = (first + last) / 2;
		if (count++, array[middle] == value)
		{
			found = true;
			position = middle;
		}
		else if (count++, array[middle] > value)
			last = middle - 1;
		else count++, first = middle + 1;
		 
	}
	
	
	return position;
	
}


Was This Post Helpful? 0
  • +
  • -

#10 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5832
  • View blog
  • Posts: 12,685
  • Joined: 16-October 07

Re: Counting the number of comparisons in an array to find a value

Posted 07 June 2011 - 12:44 PM

While the comma thing is cool, I'm not sure you need it. Also, you don't return count? What good is it, then?

For linear, you don't really need count at all, actually:
int searchList (int list[], int numElems, int value, int &count) {
	for(int i=0; i<numElems; i++) {
		if (list[i] == value) {
			count = i+1;
			return i;
		}
	}
	count = numElems;
	return -1;
}



For binary it's a little more fun, but it's almost more interesting if you don't do the comma thing.
int binarySearch(int array[], int numElems, int value, int &count) {
	int first = 0, last = numElems - 1;
	count=0;
	while (first <= last) {
		int middle = (first + last) / 2;
		count++;
		if (array[middle] == value) {
			return middle;
		} else if (array[middle] > value) {
			last = middle - 1;
		} else {
			first = middle + 1;
		}
		count++;
	}
	return -1;
}



Hope this helps.

This post has been edited by baavgai: 07 June 2011 - 12:45 PM

Was This Post Helpful? 2
  • +
  • -

#11 Mideoan  Icon User is offline

  • D.I.C Head

Reputation: 4
  • View blog
  • Posts: 77
  • Joined: 31-May 11

Re: Counting the number of comparisons in an array to find a value

Posted 07 June 2011 - 02:22 PM

I decided to go with global variables because I couldn't figure out how to use a pass by function. Here is my final code and thank you for all your help!



#include <iostream>
using namespace std;

//Function prototype
int searchList(int [], int, int);
int binarySearch(int [], int, int);
const int SIZE = 20;
// Counters
int count;
int count2;

int main()
{
	int numbers[SIZE] = {12, 13, 14, 15, 17, 21, 24, 25, 26, 29,
						 31, 36, 37, 38, 39, 45, 52, 75, 91, 95};
	
	int resultsLinear;
	int resultsBinary;
	int numberHold;
	

	// Search for a number
	cout << "Enter a number you wish to search the array for: ";
	cin >> numberHold;
	// Linear result
	{
	resultsLinear = searchList(numbers, SIZE, numberHold);

	
	
	
	if (resultsLinear == -1)
		cout << "The number you entered was not found." << endl;
	else 
	{
		cout << " Your number, " << numberHold << " was in array field " << resultsLinear << " and counted as number " 
			 <<count << " in the linear function. " << endl;
	}

	}

	// Binary result
	{
	resultsBinary = binarySearch(numbers, SIZE, numberHold);

	
	

	if (resultsBinary == -1)
		cout << "That number does not exist in this array. " << endl;
	else
	{
		cout << " That number is " << resultsBinary  << " in the array field and counted " << count2 << " times in the binary function." << endl;
	}
	system("Pause");
	return 0;

}
	system("Pause");
	return 0;
}

	





// Linear Search Algorithm
int searchList (int list[], int numElems, int value)
{
	
	int index = 0;
	int position = -1;
	bool found = false;

	

	while (index < numElems && !found)
	{
		if ((count++, list[index] == value))
		{
			found = true;
			position = index;
		}
		index++;
	}
	 
	

	return position;
	
	

	
}


// Binary Search Algorithm
int binarySearch(int array[], int numElems, int value)
{
	
	int index = 0;
	int first = 0,
		last = numElems - 1,
		middle,
		position = -1;
	bool found = false;

	

	while (!found && first <= last)
	{
		middle = (first + last) / 2;
		if (count2++, array[middle] == value)
		{
			found = true;
			position = middle;
		}
		else if (array[middle] > value)
			last = middle - 1;
		else first = middle + 1;
		 count2++;
	}
	
	
	return position;
	
}


Was This Post Helpful? 0
  • +
  • -

#12 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: Counting the number of comparisons in an array to find a value

Posted 07 June 2011 - 02:50 PM

View Postbaavgai, on 07 June 2011 - 03:44 PM, said:

For binary it's a little more fun, but it's almost more interesting if you don't do the comma thing.
int binarySearch(int array[], int numElems, int value, int &count) {
	int first = 0, last = numElems - 1;
	count=0;
	while (first <= last) {
		int middle = (first + last) / 2;
		count++;
		if (array[middle] == value) {
			return middle;
		} else if (array[middle] > value) {
			last = middle - 1;
		} else {
			first = middle + 1;
		}
		count++;
	}
	return -1;
}



Hope this helps.



See this is why I suggested using the comma trick. By my reckoning you example would get the wrong count. for example you don't count the comparison (array[middle] == value).

The reason I suggested the comma option is because you can explicitly associates a count++ which each comparison. You can easily see where the counts are being increased and why.


However, you are 100% correct that they are not needed, one just needs to ensure that the count++'s are added in the proper locations.
Was This Post Helpful? 0
  • +
  • -

#13 Munawwar  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 162
  • View blog
  • Posts: 457
  • Joined: 20-January 10

Re: Counting the number of comparisons in an array to find a value

Posted 07 June 2011 - 02:55 PM

Passing a reference can be understood with an example. Say:
void func1(int &a) { //Pass by reference
  a++;
}
void func2(int a) { //Pass by value
  a++;
}

int count=0;
func1(count); //After this statement, count becomes = 1
func2(count); //This call doesn't change the value of count


The way to think about reference is that when you pass 'count' to func1, 'count' and 'a' starts sharing the same memory block **. That means, any change done to 'a' inside func1 will reflect back to 'count'.

** Actually there is more to it. When data is casted from one data type to another, things are little different. But in the case I have shown above, the statement holds true.
Was This Post Helpful? 1
  • +
  • -

#14 Munawwar  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 162
  • View blog
  • Posts: 457
  • Joined: 20-January 10

Re: Counting the number of comparisons in an array to find a value

Posted 07 June 2011 - 03:05 PM

Quote

By my reckoning you example would get the wrong count. for example you don't count the comparison (array[middle] == value).

I believe baavgai does get it correct.

count++;
if (array[middle] == value) { //Accessing array here
    return middle;
} else if (array[middle] > value) {//Another access to array is done here
...
...
count++;


Here if array[middle] == value succeeds, then the return statement prevents the code from reaching the second count++ statement.
If it fails, then (as expected) count is incremented twice.
Was This Post Helpful? 1
  • +
  • -

#15 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: Counting the number of comparisons in an array to find a value

Posted 07 June 2011 - 03:32 PM

ah, yes. i was counting the comparison in the while..

see me reckoning is not always right. :)
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2