Puzzled.

This is a discussion on Puzzled. within the C Programming forums, part of the General Programming Boards category; Ok. I have modified my code and I get it to search and all. How can I go about taking ...

  1. #1
    Registered User
    Join Date
    Nov 2007
    Posts
    69

    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

  2. #2
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    You seemed to have used an invisible font... I can't see any code.

  3. #3
    The larch
    Join Date
    May 2006
    Posts
    3,573
    If the array is unsorted, can you find the maximum and minimum value in it? Finding values closest to a value should not be that different.

    If your binary search returns the pointer to the item where the search ended, then - probably depending on your implementation - it should point to either the closest bigger or smaller value. Do not forget that the value you are looking for might be smaller or larger than any value in the array.

    I think I found your original thread and you had an interesting statement there:
    User will input a target number and will search for it in the array. However the array could be sorted or unsorted. I would like to test for that in oder to determine which method to use.
    Now, you'll need a full pass over the array to determine if it is sorted. With a single pass over the array you could have already determined both whether the value is there and found the two closest values - and you don't need to go to the end if you are lucky and the value is there, somewhere in the middle.

    That is, as far as complexity is concerned, a simple linear search might be just fine. (Unless the linear search would be so much more expensive that doing the sortedness test and binary search can pay off - guess that depends on many things.)
    Last edited by anon; 01-21-2008 at 11:27 AM.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    In a sorted list of numbers, go down the list sequentially, until the number you're now checking, is > your target. If it's in an array, let's call that point Array[i]. That will be the smallest number that is > your target.

    And since the array is sorted, and you already know that the list doesn't include your target number, then Array[i - 1] will be the largest number in the list that is < your target. This is only true if your target is between the minimum and the maximum value of your numbers in the Array[]
    Last edited by Adak; 01-21-2008 at 11:28 AM.

  5. #5
    Registered User
    Join Date
    Nov 2007
    Posts
    69

    understand but could you help more?

    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

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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).

  7. #7
    Registered User
    Join Date
    Nov 2007
    Posts
    69
    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?

  8. #8
    Registered User
    Join Date
    Nov 2007
    Posts
    69
    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.

  9. #9
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by silhoutte75 View Post
    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 = &mid;
    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?

  10. #10
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by silhoutte75 View Post
    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])
    Quote Originally Posted by silhoutte75 View Post
    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.

  11. #11
    Registered User
    Join Date
    Nov 2007
    Posts
    69

    ok

    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.

  12. #12
    Registered User
    Join Date
    Nov 2007
    Posts
    69
    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.

  13. #13
    The larch
    Join Date
    May 2006
    Posts
    3,573
    You might try turning on compiler warnings.

    I get
    Untitled1.c: In function `main':
    Untitled1.c:39: warning: too few arguments for format

    Untitled1.c: In function `generNum':
    Untitled1.c:85: error: 'for' loop initial declaration used outside C99 mode
    Untitled1.c: In function `printNum':
    Untitled1.c:106: error: 'for' loop initial declaration used outside C99 mode
    Untitled1.c: In function `bubbleSort':
    Untitled1.c:135: error: 'for' loop initial declaration used outside C99 mode
    Untitled1.c:138: error: 'for' loop initial declaration used outside C99 mode

    Untitled1.c: In function `searchSetUp':
    Untitled1.c:170: warning: suggest parentheses around assignment used as truth value
    Untitled1.c:164: warning: unused variable `last'
    Untitled1.c: In function `binarySearch':
    Untitled1.c:220: warning: statement with no effect
    Untitled1.c: In function `seqSearch':
    Untitled1.c:250: warning: suggest parentheses around assignment used as truth value

    Execution terminated
    The C99 warnings are benign but the rest point to errors in your code.

    Code:
    else (a == b); {
         //yada yada
    }
    This has been pointed out. Else doesn't take a condition and the else block ends with the semicolon, leaving you with a statement that has no effect. What follows in the braces is executed anyway - it is not the else block!
    Last edited by anon; 01-21-2008 at 04:14 PM.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  14. #14
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by silhoutte75 View Post
    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.)

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 4
    Last Post: 07-15-2005, 04:10 PM
  2. Puzzled
    By fkheng in forum C Programming
    Replies: 5
    Last Post: 06-22-2003, 09:56 PM
  3. Puzzled
    By sketchit in forum C Programming
    Replies: 3
    Last Post: 10-30-2001, 07:11 PM
  4. Still puzzled [I hope this formatted]
    By sketchit in forum C Programming
    Replies: 2
    Last Post: 09-28-2001, 12:26 AM
  5. Still puzzled
    By sketchit in forum C Programming
    Replies: 1
    Last Post: 09-27-2001, 05:09 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21