Thread: Puzzled.

Ok. I have modified my code and I get it to search and all.

How can I go about taking the target number I am searching for and create a separate search if the target is not found, so that I can find the largest number less than the target and the smallest number greater than the target?

I know that in the if ... else statement is the key. But I'm stumped in initalizing that particular search. I have the found pretty much down but I puzzled on the rest. Depending on whether or not its a sorted array tells me which method of search to us. Binary or Sequential.

Suggestions would be helpful for getting on track.

Thanks
Silhoutte75

You seemed to have used an invisible font... I can't see any code.

Code:

/*===============================searchSetUp=====================================
Test to see if array has been sorted or not.
    Pre: the array
	Post: determines if sorted then search binary method or
	                 if unsorted then search sequentially.
 */

void searchSetUp (int* randNum, int sorted, int* target2)
{
	//Local Declarations	  
//	  int* larNum;
//	  int* smallNum;
	  int last = (ARY_SIZE - 1);

    //Statements
	  printf("\nPlease indicate the number you wish to search for.\n");
	  scanf ("\n\t%d", target2);
	  
	  if(sorted = 0)
		  binarySearch(randNum, sorted, target2);
	  else 
		  seqSearch (randNum, sorted, target2);

	  return;
}//searchSetUp
/*=================================binarySearch================================
Search an sorted array using the binary method.
   Pre - array is recieved as a list of numbers
         end is index to last element in array
		 target is number being sought
		 location of number(locNum) the address or index to location of target.
   Post - Found: locNum = index to target
                 return 1 (found)
		  Not Found: locNum1 = element index below target
		             locNum@ = element index above target
					 return o (not found)
*/

int binarySearch (int* randNum, int sorted, int* target2)
{
	//Local declarations
	  int first;
	  int mid;
	  int last;
	  int* locIndex;

	//Statements
	  first = 0;
	  last  = (ARY_SIZE - 1);
	  while (first <= last)
	     {
         mid = (first <= last);
		 if (*target2 > randNum[mid])
		    // look in upper half
			first = mid + 1;
		 else if (*target2 < randNum[mid])
			// look in lower half
			last  = mid - 1;
		 else 
		   // found equal: force exit
		    first = last + 1;
	     }//end while
	  locIndex = &mid;
        if (*target2 == randNum[mid])
	{
	printf("Target Found.");
	return 1;
	}
        else (*target2 != randNum[mid]);
	 printf("Target NOT Found.");
                 return 0; 
} // binarySearch
/*=================================seqSearch===================================
Search an unsorted array using the sequential method.
   Pre - array is recieved as a list of numbers
         end is index to last element in array
		 target is number being sought
		 location of number(locNum) the address or index to location of target.
   Post - Found: locNum = index to target
                 return 1 (found)
		  Not Found: locNum1 = element index below target
		             locNum2 = element index above target
					 return 0 (not found)
*/

int seqSearch ( int* randNum, int sorted, int* target2)
{
	//Local Declarations
	int finder;
	int found;
	int* locIndex;

	//staements
	  finder = 0;
	  while (finder < ARY_SIZE && *target2 != randNum[finder])
		  finder++;
	  if (found = (*target2 == randNum[finder]))
	   {
	      locIndex = &finder;
	      printf("Target Found at %d\n"); 
	      scanf ("%d", randNum[finder]);
	      return 1;
	   }
	  else 
	     return 0;
}//seqSearch

I think that I'm getting it but it isstill kind of foggy.

let's say my target is 345
but it's not in the array.

would a for or if else staements work. I know the logic for the math but can't seem to pull out the computer math logic.

345 = t
t < (t-1) = i greatest number less than target

t > (t+1) = i smallest number greater than target

Many things here:

Code:

if (sorted = 0)

This should throw a warning, because you're doing an assignment and not a comparison.

Code:

mid = (first <= last);

Hopefully this is cut'n'paste gone horribly wrong.

Code:

else (*target2 != randNum[mid]);

You don't give conditions on an else statement. You should get a warning here, too.

Your binary search and sequential search return values, but you don't use them.

If a number is missing, the mid index in your binary search will be either just too low or just too high. In the sequential search, you have no choice but to go through the array (if you want, you can combine it with the first pass, but since the array is unsorted, you can't get there logically).

Ok my searches work but I'm trying to get the index at which the target is when found or the index of the target of the largest number less than the target and vice versa.

I am unsure how to ever approach this idea. Could you help?

Code:

if (sorted = 0)

if my flag that allows my program to know whether or not the program is sorted. That part of code was not shown here but is in the other potion.

Code:

mid = (first <= last);

I think this was supposed to be

Code:

mid = (first  + last) / 2

that makes more logical since.

Code:

else (*target2 != randNum[mid]);

worked in the code but not exactly sure becuase I have not tested it with a print staement as of yet.

Originally Posted by silhoutte75

Ok my searches work but I'm trying to get the index at which the target is when found or the index of the target of the largest number less than the target and vice versa.

I am unsure how to ever approach this idea. Could you help?

Why do you think the person who wrote the code wrote the line

Code:

locIndex = ∣

What does that accomplish in terms of "getting the index at which the target is when found"?

Again, finding the surrounding values is trivial in a binary search. Hint: consider the array
1 3 5 7 9.
What index do you stop at when you do a binary search for 2? For 8? For 6? What can you conclude from this?

Originally Posted by silhoutte75

Code:

if (sorted = 0)

if my flag that allows my program to know whether or not the program is sorted. That part of code was not shown here but is in the other potion.

No it doesn't. Look at it again. Compare with

Code:

if (*target2 == randNum[mid])

Originally Posted by silhoutte75

Code:

else (*target2 != randNum[mid]);

worked in the code but not exactly sure becuase I have not tested it with a print staement as of yet.

No it didn't. (1) the bit of code in the parentheses is not a statement, but an expression, which will evaluate and throw away its value since you don't do anything with it and (2) since you don't have braces it's the only thing in your else clause, despite your (apparent) indentation.

I believe that when I wrote this I was trying to reference the index but I have allocated the address of the data and where it is store. It has not given me my index which I so desperately what to do.

ok here is the entire code. I need someone to help me pick it apart and fix it. It prints two
"your Choice statements every run. Which is weird and can't figure out why. I need to complete this and I'm running out of time. Worked on this 2 weeks and I have come to a road block now.

Code:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <ctype.h>

#define ARY_SIZE 50

//Function Declarations
void functionUse (char choice);
void generNum (int* randNum);
void printNum (int* data, int numItems, int countPerLine);
void bubbleSort (int* randNum);
void searchSetUp (int* randNum, int sorted, int* target2);
int binarySearch (int* randNum, int sorted, int* target2);
int seqSearch ( int* randNum, int sorted, int* target2);

int main (void)
{
	//Local Declaration
	char letter;
	char select;
                int randNum [ARY_SIZE];
	int sorted;
	int target;
		
		
	//Statements
	printf ("\t\tMenu\t\t\n");
	printf ("=================================================\n\n");
	printf ("Select one of the following options:\n");
	printf ("\t F. Fill array with a random number series\n");
	printf ("\t P. Print the array\n");
	printf ("\t S. Sort the array\n");
	printf ("\t Q. Query the array\n");
	printf ("\t Z. Terminate the program\n");
	
	do
	 {
	   printf ("\tYour choice is:  %2c");	
	   scanf ("%c", &letter);

	   select = letter;
	   select = tolower(select);

	  if (select == 'f')
	   {
                    printf ("\t Fill\n");
	    generNum (randNum);
	   }
	  else if (select == 'p')
	   {	
	    printf ("\t Print\n");
	    printNum (randNum, ARY_SIZE, 10);
	   }
	  else if (select == 's')
	  {
	    printf ("\t Sort\n");
	    bubbleSort (randNum);
	    sorted = 0;
	  }
	  else if (select == 'q')
	  {
	    printf ("\t Query\n");
	    searchSetUp (randNum, sorted, &target);
	  }
	 }while ( select != 'z');
	printf ("\tYou are finished.\n");
		
	system("PAUSE");
	return 0;
} //main
/*==============================generNum======================================
Generate random numbers that will be used to fill an array.
     Pre: randNum array is to recieve the random numbers generated.
	 Post: filled array
*/

void generNum (int* randNum)
{
	//local Declarations
	 int* aRandNo;
	 
               //statements
	 srand(time (NULL));
	 for (int i =0; i < ARY_SIZE; i++)
	   {
	   aRandNo = randNum+i;
	   *aRandNo = rand() % 999 + 1;		   
	   }//for
     return;
}//generNum
/*===============================printNum=======================================
Prints the data of the array.
   Pre data: a filled array
       last: last elements indicated by an index
	   countPerLIne: number of elements on a line
   Post: data printed
*/
void printNum (int* data, int numItems, int countPerLine)
{
	//Local Declarations
	  int elemPrinted = 0;

               //Statements
	  printf ("\n");
	  for (int i = 0; i < numItems; i++)
          {
	 elemPrinted++;
	 printf ("%3d ", *(data+i));
	 if (elemPrinted >= countPerLine)
	    {
	   printf ("\n");
	   elemPrinted = 0;
	    }//if
	     }//for
	  printf ("\n");
	  return;
} // printNum
/*=================================bubbleSort=================================
Sort array using bubble sort. Elements are compared and exchanged until list 
is in order.
   Pre: minimun of 1 random number.
        end contains index of last element in randNum array.
   Post: randNum array is rearranged in sequence low to high.
*/

void bubbleSort (int* randNum)
{
	//Local Declarations
	  int temp;
	  int* address;

    //Statements
	  //outer Loop
	  for (int initial = 0; initial <= ARY_SIZE; initial++)
	     {
	       //Inner loop. Bubble starts at end and moves up 1 element each pass.
	          for (int mover = (ARY_SIZE - 1);
	                mover > initial;
		mover--)
	             if (*(randNum +mover) < *(randNum +(mover - 1)))
		{
		 temp        = *(randNum +mover);
		 address     = randNum +mover;
		 *address    = *(randNum +(mover - 1));
		 address     = randNum +(mover - 1);
		 *address    = temp;
		 }//if - exchange of numbers 
	     }//for initial
	  return;
} //bubblesort
/*===============================searchSetUp=====================================
Test to see if array has been sorted or not.
    Pre: the array
	Post: determines if sorted then search binary method or
	                 if unsorted then search sequentially.
 */

void searchSetUp (int* randNum, int sorted, int* target2)
{
	//Local Declarations	  
//	  int* larNum;
//	  int* smallNum;
	  int last = (ARY_SIZE - 1);

    //Statements
	  printf("\nPlease indicate the number you wish to search for.\n");
	  scanf ("\n\t%d", target2);
	  
	  if(sorted = 0)
		  binarySearch(randNum, sorted, target2);
	  else 
		  seqSearch (randNum, sorted, target2);

	  return;
}//searchSetUp
/*=================================binarySearch================================
Search an sorted array using the binary method.
   Pre - array is recieved as a list of numbers
         end is index to last element in array
		 target is number being sought
		 location of number(locNum) the address or index to location of target.
   Post - Found: locNum = index to target
                 return 1 (found)
		  Not Found: locNum1 = element index below target
		             locNum@ = element index above target
					 return o (not found)
*/

int binarySearch (int* randNum, int sorted, int* target2)
{
	//Local declarations
	  int first;
	  int mid;
	  int last;
	  int* locIndex;

	//Statements
	  first = 0;
	  last  = (ARY_SIZE - 1);
	  while (first <= last)
	     {
                       mid = (first + last) / 2;
	         if (*target2 > randNum[mid])
	            // look in upper half
		first = mid + 1;
	         else if (*target2 < randNum[mid])
	           // look in lower half
		last  = mid - 1;
	         else 
	           // found equal: force exit
	                first = last + 1;
	     }//end while
	  locIndex = &mid;
        if (*target2 == randNum[mid])
         {
             printf("Target Found.");
             return 1;
         }
       else (*target2 != randNum[mid]);
         {  
          printf("Target NOT Found.");
          return 0; 
         }
} // binarySearch
/*=================================seqSearch===================================
Search an unsorted array using the sequential method.
   Pre - array is recieved as a list of numbers
         end is index to last element in array
		 target is number being sought
		 location of number(locNum) the address or index to location of target.
   Post - Found: locNum = index to target
                         return 1 (found)
             Not Found: locNum1 = element index below target
	               locNum2 = element index above target
	               return 0 (not found)
*/

int seqSearch ( int* randNum, int sorted, int* target2)
{
	//Local Declarations
	int finder;
	int found;
	int* locIndex;

	//staements
	  finder = 0;
	  while (finder < ARY_SIZE && *target2 != randNum[finder])
		  finder++;
	  if (found = (*target2 == randNum[finder]))
	   {
	      locIndex = &finder;
	      printf("Target Found at %d\n", randNum[finder]); 
	      
	      return 1;
	   }
	  else 
                     return 0;
}//seqSearch

be brutally nice.

Originally Posted by silhoutte75

I believe that when I wrote this I was trying to reference the index but I have allocated the address of the data and where it is store. It has not given me my index which I so desperately what to do.

So try *locIndex = num instead. (In other words, you don't want to change the pointer locIndex, you want to change the value pointed to; so, we dereference locIndex and assign.)