Search

keystoneman · 10-06-2004, 11:23 AM

I'm workin on a porblem that basically compares a linear search to a binary search, what I want to do is be able to check for 5 different values, but this is where I run into a problem. When ever I start to use arrays and loops it starts to mess up my output.

Here is some code that works perfect, but it only does the search for one value ...

Code:

// Linear and Bin search
// ERIC LILLY

#include <iostream>
#include <stdlib.h>
#include <cstdlib>
using namespace std;

void swap2(int&m, int&n);

void main()
{
	int a [10]={40,60,30,70,90,80,5,25,95,100};
	int k;
	bool notfound;
	int searchvalue;
	int probes=1;
	int probes2=1;
	int temp;
	bool swap;
	int searchpos;
	int low = 0;
	int high = 9;
	int linprob;
	int binprob;



   cout<<"Outputs for the array"<<endl<<endl;
   for (k = 0; k <10; k ++)
	{
		cout<<a[k]<<endl;
	}
       cout<<""<<endl<<endl;


	

{
	{
	
	cout<<"Please enter an integer:   ";
	cin>>searchvalue;
	cout<<""<<endl<<endl;



// linear search

	notfound = true;
	k = 0;

	while(k < 10 && notfound)
	{
		if(searchvalue != a[k])
		{	k++;
			probes ++;
		}
		else
			notfound = false;
	}

	if( notfound == false )
		linprob=probes;
	else
		linprob=-1;
	


// sort array a
	  do
   {
	   swap = false;
		for (int count=0; count<(10-1); count++)
		{
			if (a[count]>a[count+1])
			{
				temp = a[count];
				a[count] = a[count+1];
				a[count+1]=temp;
				swap=true;
			}

		}
	}while (swap);

// binary search
  
 
   searchpos = (low + high) / 2;
	
       while((a[searchpos] != searchvalue) && (low <= high))
       {
              
			probes2++;
              if (a[searchpos] > searchvalue)               
             {                                                         
                    high = searchpos - 1;     
             }                                                         
             else                                                     
            {                                                          
                   low=searchpos + 1;        
            }
             searchpos = (low + high) / 2;
       }
       if (low <= high)
            binprob=probes2;
       else
             binprob=-1;

	}
	cout<<"Value            Linear Search          "<<
"Binary Search"<<endl;
	
	
	
		cout<<searchvalue<<"               "<<linprob<<"                      "<<binprob<<endl;
	

cout<<endl<<endl;
}
}
void swap2(int &x, int &y)
{
    int temp;

    temp = x;
    x = y;
    y = temp;
}

And here we have my code that messes up because i'm trying to use loops and arrays to get 5 values to input and output ...

Code:

// Linear and Bin search
// ERIC LILLY

#include <iostream>
#include <stdlib.h>
#include <cstdlib>
using namespace std;

void swap2(int&m, int&n);

void main()
{
	int a [10]={40,60,30,70,90,80,5,25,95,100};
	int k,i;
	bool notfound;
	int searchvalue [5];
	int probes=1;
	int probes2=1;
	int temp;
	bool swap;
	int searchpos;
	int low = 0;
	int high = 9;
	int linprob [5];
	int binprob [5];



   cout<<"Outputs for the array"<<endl<<endl;
   for (k = 0; k <10; k ++)
	{
		cout<<a[k]<<endl;
	}
       cout<<""<<endl<<endl;


	

{
	
	for(i=1;i<=5;i++)
	{
		probes = 1;
		probes2 = 1;
	cout<<"Please enter an integer:   ";
	cin>>searchvalue [i];
	cout<<""<<endl<<endl;



// linear search

	notfound = true;
	k = 0;

	while(k < 10 && notfound)
	{
		if(searchvalue [i] != a[k])
		{	k++;
			probes ++;
		}
		else
			notfound = false;
	}

	if( notfound == false )
		linprob [i]=probes;
	else
		linprob [i]=-1;
	


// sort array a
	  do
   {
	   swap = false;
		for (int count=0; count<(10-1); count++)
		{
			if (a[count]>a[count+1])
			{
				temp = a[count];
				a[count] = a[count+1];
				a[count+1]=temp;
				swap=true;
			}

		}
	}while (swap);

// binary search
  
 
   searchpos = (low + high) / 2;
	
       while((a[searchpos] != searchvalue [i]) && (low <= high))
       {
              
			probes2++;
              if (a[searchpos] > searchvalue [i])               
             {                                                         
                    high = searchpos - 1;     
             }                                                         
             else                                                     
            {                                                          
                   low=searchpos + 1;        
            }
             searchpos = (low + high) / 2;
       }
       if (low <= high)
            binprob [i]=probes2;
       else
             binprob [i]=-1;

	}
	cout<<"Value            Linear Search          Binary Search"<<endl;
	
	for (i=1;i<=5;i++)
	{
		cout<<searchvalue [i]<<"               "<<
linprob [i]<<"                      "<<binprob [i]<<endl;
	}

cout<<endl<<endl;
}
}
void swap2(int &x, int &y)
{
    int temp;

    temp = x;
    x = y;
    y = temp;
}

joe_bruin · 10-06-2004, 02:42 PM

first, fix this:

Code:

for(i=1;i<=5;i++)
{
	probes = 1;
	probes2 = 1;
	cout<<"Please enter an integer:   ";
	cin>>searchvalue [i];
	cout<<""<<endl<<endl;

i should go from 0 to 4 (inclusive), otherwise you're going out of bounds on array searchvalue.

keystoneman · 10-06-2004, 03:02 PM

I tried that and now it only accepts 4 integers to use in the seach so the fifth is extremly messed up in the output, and also I think the problem may be somewhere else because for the first four the outputs are not correct.

But thanx for the input

Valmont · 10-06-2004, 03:21 PM

Okidoky.
Implementing so many details in the main() function makes code very hard to read. C++ (just like C) has the disadvantage that it is hard to read (for those who didn't write the code) anyway. So what I did is basically wrote your code from scratch, without looking at your code. The first tangible result is that I need much less variables to start with. But more importantly, the complete application has become much more readable. Readable in the sense that I've split all the details in their own specialized functions. If a function meets the requirements, then that function doesn't need any attention in the future.

What you should be aware of is that my binary and linear search methods are suitable for both multiple searches (in a loop) and for single searches. No need to program almost-identical algorithms this way.
The second major thing that I did is to use std::sort(). Note that factors regarding sorting algorithms was *not* one of the requirements as you posted. So lets use std::sort() since it is there for us already. Obviously I needed to add the <algorithm> header.

Another thing what I did, is using int main() ... return 0; instead of void main(). Lets try to do the very basics right from the beginning. It is only 2 seconds more work :).
However, I've decided to usesystem("PAUSE"); as an optional anti-console-flash method. Change it yourself into a correct method. Notice how I am an anti system( ) person. Lets try to do the very basics right from the start, like I mentioned earlier :)

The code follows below. I think you'll undestand it. But feel free to ask about it any time:

Code:

/*** main.cpp ***/

#include <iostream>
#include <cstdlib> //system("PAUSE")
#include <algorithm> //std::sort()

using namespace std;

//Globals are dangerous. But for entry level study it will do.

void swap2(int&m, int&n);
void displaySearchRequest(unsigned);
int find_first_linear(int*, int, int);
int find_first_binary(int*, int, int);
void displayArray(int*, int);

int linLogicPos[5];
int binLogicPos[5];
int searchValue[5];

//Lets keep the amount of numbers to be found in a constant. Change this value
//only if you would like to change the amount of numbers to be found.
const unsigned amount = 2;

int  main()
{
   int theArray [10]={ 40,60,30,70,90,80,5,25,95,100 };
  int size = sizeof(theArray) / sizeof(*theArray);
  cout<<"Initial array:\t";
  displayArray(theArray, size);
   cout<<endl<<endl;
   
   //Engage menu to ask for number(s) to be found.
   displaySearchRequest(amount);
   //Find by Linear.
   for(int i = 0; i < amount; ++i)
      linLogicPos[i] = find_first_linear(theArray, searchValue[i], size);

   //Find by Binary, but we need to sort first.
   //Lets use the STL sort routine since it is not relevant to the analisys.
   //You could always implement your own sort routine if needed.
  sort(theArray, theArray+10);
  for(int i = 0; i < amount; ++i)
      binLogicPos[i] = find_first_binary(theArray, searchValue[i], size);
   
   //Display the final results.
   cout<<"VALUE\tLINEAR\tBINARY"<<endl;
   for (int i = 0; i < amount; ++i)
      cout<<searchValue[i]<<"\t"<<linLogicPos[i]<<"\t"<<binLogicPos[i]<<endl;

  system("PAUSE");
  return 0;
}

/*=========================================================*/

void displayArray(int* array, int size)
{
   for (int k = 0; k < size; ++k)
      cout<<array[k]<<" ";
}

/*=========================================================*/

// k = amount of numbers to search for.
void displaySearchRequest(unsigned k)
{
   for(int i = 0; i < k; ++i)
   {
      cout<<"Please enter an integer: ";
      cin>>searchValue[i];
   }
}

/*=========================================================*/

int find_first_linear(int* theArray, int x, int size)
{
   int pos(-1);
   for ( register unsigned k = 0; k < size; ++k)
      if( x == theArray[k] )
         { pos = k; break; }

   //Return logical position of found value (-1 if not found).
   return pos;
}

/*=========================================================*/

int find_first_binary(int* a, int x, int size)
{
   int low = 0, high = size - 1;
   while( low <= high )
   {
      int mid = ( low + high ) / 2;
      if( a[mid] < x )
            low = mid + 1;
      else if( a[mid] > x )
            high = mid - 1;
      else
      { return mid; }//Found.
   }
   { return -1;}  //Not found.
}

sde · 10-06-2004, 03:46 PM

wow, hey val, what did you use to color the code? i'm thinking that would be great to incorporate into the new forums.

something like [c] [/c]

Valmont · 10-06-2004, 03:52 PM

Quote:

Originally posted by sde
wow, hey val, what did you use to color the code? i'm thinking that would be great to incorporate into the new forums.

something like [c] [/c]

Some crappy console proggy I made a few months ago. It is buggy though. I need to re-do the algorithms and make it os independant as much as possible. Most likely using wxWindows. Not Qt.
On the net you'll find code-to-html converters though. I don't know what to do with it but perhaps it is interesting for you.

keystoneman · 10-06-2004, 05:31 PM

Hey Val, I have been messing around with yoru code editing it and such, I havent touched you binary part because i'm not sure if its right or wrong, I believe its wrong but then again what do I know ...

Here is a smaple output I generate ...

Code:

Initial array:  40 60 30 70 90 80 5 25 95 100 101

Please enter an integer: 60
Please enter an integer: 80
VALUE   LINEAR  BINARY
60      2       4
80      6       6
Press any key to continue . . .

When I entered the 60 with a bin search should't it produce a 2, and the bin search for 80 shouldnt that produce a 1; I always thought the bin search cut the array in half checking it, and if it wasnt found cutting it again, until it was found?

Am I wrong?

Valmont · 10-06-2004, 06:17 PM

Quote:

When I entered the 60 with a bin search should't it produce a 2

No, because the value returned is the INDEX of the SORTED array.
You will need to backup the unsorted array if you want to know its index from the unsorted array.

Quote:

bin search for 80 shouldnt that produce a 1

No. It should return the index of the SORTED array.

Quote:

I always thought the bin search cut the array in half checking it, and if it wasnt found cutting it again, until it was found?

Yes, but not relevant. Usually you return the index of the sorted array, or the unsorted array. It doesn't make sense to return the index of the "cut-array" IF found, since the index is always 0 ( by design for binary search).

A last note:
Your output isn't correct as you posted it above. Note that the algorithms return the index of arrays. Arrays start at index "0" by default. The correct output should be:
VALUE LIN BIN
60 1 4
80 5 6

For example, 60 is at PHYSICAL location "2". But since arrays start at index 0, the correct output is 1.
Same goes for 80.
So LOGICAL = PHYSICAL -1 by default.

I notice you added the number 101 to your original array. In that case make sure it can hold 11 numbers (10 in the original code remember?).
Solve it for good by typing this in main():
int theArray []={ 40,60,30,70,90,80,5,25,95,100, 101 };

keystoneman · 10-06-2004, 08:04 PM

Thanks for clearing that up