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.

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:

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

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[]

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.

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 = ∣

---

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?

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.

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.

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!

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