# Puzzled.

• 01-21-2008
silhoutte75
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
• 01-21-2008
Dino
You seemed to have used an invisible font... I can't see any code.
• 01-21-2008
anon
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.

Quote:

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.)
• 01-21-2008
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[]
• 01-21-2008
silhoutte75
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
• 01-21-2008
tabstop
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).
• 01-21-2008
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?
• 01-21-2008
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.

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.
• 01-21-2008
tabstop
Quote:

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 = &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?
• 01-21-2008
tabstop
Quote:

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])`
Quote:

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.
• 01-21-2008
silhoutte75
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.
• 01-21-2008
silhoutte75
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.
• 01-21-2008
anon
You might try turning on compiler warnings.

I get
Quote:

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!
• 01-21-2008
tabstop
Quote:

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.)