Functions (HELP!)

Hi! I'm new to C-programming (Computer Science freshman) and we have this one assignment where we have to use functions to determine if a user-input array is arranged (monotonically non-increasing/non-decreasing) or not. If it's arranged, we have to use another function to perform a binary search to look for a "key" integer in the array. If it's not arranged in any way, we have to use linear search. I got the binary search and linear search down. I think I also got how to determine if it's arranged or not. What I don't understand is how to use them in functions and how to call them out in my main. HELP! :(

Code:

---

#include <stdio.h>
#include <conio.h>



int main()
{

    //scans for length of array
    int n;
    scanf("%d", &n);

    //gets elements of array
    int arr[n];
    int i;
    for(i=0;i<n;i++)
    {
        scanf("%d",&arr[i]);
    }

    //gets target/key
    int key;
    scanf("%d", &key);

    //check if the elements are sorted in any order
    int option;
    option = is_ordered();

    //if elements are sorted, use binary search
    if(option == 0 || option == 1)
        binary_search();
    else
        linear_search();
    //if target/key is found in list, output "FOUND at index i"
    //for some 0<=i<n, ouput "NOT FOUND"

return(0);
}

int is_ordered(int arr[], int option)
{
    int i;
    int n;
    for(i=0;i<n;i++)
    {
        if(arr[i] <= arr[i+1])
        option = 0; //non-increasing
        else if(arr[i] >= arr[i+1])
        option = 1; //non-decreasing
        else
        option = -1; //no order --> LINEAR SEARCH
    }
    return (option);
}

int linear_search(int arr[], int n, int key)
{
    int i;
    for(i=0;i<n;i++)
        {
            if(key==arr[i])
            printf("FOUND at index %d\n", i);
            else
            printf("Not found\n");
        }
    return(0);
}

int binary_search(int arr[], int n, int key)
{
    int first, last, middle;

    first = 0;
    last = n - 1;
    middle = (first+last)/2;

    while( first <= last )
    {
        if ( arr[middle] < key )
            first = middle + 1;
        else if ( arr[middle] == key )
        {
            printf("%d found at index %d\n", key, middle+1);
            break;
        }
        else
            last = middle - 1;

        middle = (first + last)/2;
    }
    if ( first > last )
        printf("Not found\n", key);

    return 0;
}

---

This is my code so far. When I compile it, no errors come out. But when I try to run it, it won't work. It only works until the part where I enter the "key" I need to look for.

Just above the main() function (which should be the first function in your program's code), you will have a function prototype for each of the functions in your program.

The very first line of the function, can also be used as this prototype, for example:


This is the first line of a function in your program:

Code:

---

int is_ordered(int arr[], int option)

---

and this would be the function prototype for that function:

Code:

---

int is_ordered(int arr[], int option); //<<---note the semi-colon

---

The name of the variable, is optional, so "int option" could be just "int" in the prototype, but it's OK to leave it as "int option", also.

To call the is_ordered function, you would use:

Code:

---

int yourVariable;

yourVariable = is_ordered(arr, option);

---

"yourVariable" "catches" the return value from is_ordered (otherwise it would be lost). "arr" is the pointer to the array arr[]. All array names serve as constant pointers to their base element, in C. Note that &arr, or arr[] would be an error in the call, that would cause the compiler to stop (a fatal error).

"option" would be a COPY of the "option", not the same option as in the calling function (even though it has the same name, the scope is completely different). If you want to permanently change the value of "option" inside the is_ordered() function, you need to pass a pointer to option: (or it's memory address).

It's important to remember that all arrays degrade to just a pointer to an array, when passed to other functions - so it's common to also pass the size of the array, as well.

Something like:

Code:

---


#define SIZE 100

---

Where "SIZE" is placed above main() (right below the #included file list is most common), can help. if arr[SIZE] is used, then SIZE can be accessed by all your functions, without being a parameter. It is global in scope, as they say.

Really, you got no feedback from the compiler? I did. You need to fix all of these things:

Quote:

---

-------------- Build: Debug in foo ---------------

Compiling: main.c
C:\Users\Josh2\Documents\foo\main.c: In function 'main':
C:\Users\Josh2\Documents\foo\main.c:27: warning: implicit declaration of function 'is_ordered'
C:\Users\Josh2\Documents\foo\main.c:31: warning: implicit declaration of function 'binary_search'
C:\Users\Josh2\Documents\foo\main.c:33: warning: implicit declaration of function 'linear_search'
C:\Users\Josh2\Documents\foo\main.c: In function 'is_ordered':
C:\Users\Josh2\Documents\foo\main.c:44: warning: 'n' is used uninitialized in this function
Linking console executable: bin\Debug\foo.exe
Output size is 60.51 KB
Process terminated with status 0 (0 minutes, 0 seconds)
0 errors, 4 warnings

---

Write prototypes of functions you want to write. It's technically required for the code that you have, and it will let the compiler catch a ton of problems.

It helps me stay productive in my development process to compile and run separately so I get a chance to fix warnings. If you really don't want to do that configure your compiler to treat warnings as errors.

do you mean I should have this just before my int main():

Code:

---

#include <stdio.h>
#include <conio.h>

int is_ordered(int arr[], int option);
int linear_search(int arr[], int n, int key);
int binary_search(int arr[], int n, int key);

int main()
{

---

? I'm so sorry! I feel so incompetent, I never understand anything in our lessons :confused:

There are a few things you haven't understood.

Arguments are passed by value to functions. That means changes of arguments inside a function are local to a function. So

Code:

---

void foo(int x)
{
    x = 42;    /*  The x in here has the same name, but is a distinct entity from the x in main() */
}

int main()
{
    int x = 5;
    foo(x);
      /*  x will still be 5 here */
}

---

In your function is_ordered(), the changes of "option" are actually local to the function. However, you happen to be returning the value to the caller (via "return order"), so you have accidentally cancelled that coding error out. If you return something else (say 42), then THAT is the value that option, inside main(), will receive.

If you want to change the value of an argument, pass a pointer.

Code:

---

void foo(int *x)
{
    *x = 42;    /*  The x in here has the same name, but is a distinct entity from the x in main() */
}

int main()
{
    int x = 5;
    foo(&x);
      /*  x will still be 42 here */
}

---

The first few lines of your function is_ordered is also broken

Code:

---

int is_ordered(int arr[], int option)
{
    int i;
    int n;
    for(i=0;i<n;i++)    /*  Danger, danger.  n is uninitialised */

---

n is an uninitialised value. Accessing the value of an uninitialised variable gives undefined behaviour (anything is allowed to happen, including reformatting your hard drive). Again, this n has no relationship whatsoever to other variables named n in other parts of your code (eg the n inside main(), the argument of binary_search(), etc etc).

Technically you can make prototypes anywhere, but the best place is under the #include's, always. And in the file that contains main(), prototypes should additionally be before that. ... And arranged alphabetically. ... Well, maybe not that last one.

Compiling with a higher warning level would point out some errors at compile time. (On gcc, try gcc -W -Wall )

You need function declarations above main, like this:

Code:

---

int is_ordered(int arr[], int n);
int linear_search(int arr[], int n, int key);
int binary_search(int arr[], int n, int key, int order);

---

Notice that in is_ordered I changed option to n. is_ordered should be defined like this:

Code:

---

int is_ordered(int arr[], int n)
{
    int option = 0;
    int i;
    for (i = 0; i < n; i++)
    {
        // do something clever here
    }
    return option;
}

---

I left out your logic because it is wrong. Firstly, i + 1 accesses outside the array. Secondly, even if that was fixed, the algorithm would just return the order of the last two elements. You need to think about this algorithm some more. And it seems most natural to me to return 1 for non-decreasing, -1 for non-increasing, and 0 for unordered.

Also, the action of your binary search needs to be different depending on whether the order is non-decreasing or non-increasing. So I added an order parameter to the declaration.

Quote:

---

Originally Posted by ayizkatya

do you mean I should have this just before my int main():

Code:

---

#include <stdio.h>
#include <conio.h>

int is_ordered(int arr[], int option);
int linear_search(int arr[], int n, int key);
int binary_search(int arr[], int n, int key);

int main()
{

---

? I'm so sorry! I feel so incompetent, I never understand anything in our lessons :confused:

---

It takes a good deal of work to learn C (or any language for that matter).

Yes, that looks right - and if you CHANGE the function parameters, then you will also need to CHANGE the function prototype, so it again matches up with the actual first line of the function.

The general rule is:

start writing your new function. When you are ready to start compiling that new function, just copy the first line of the function, paste it above main(), and add a semi-colon onto the end of that line, for the prototype.

That will give you a correct prototype, every time. Repeat that copy paste, and add a semi-colon to the end of the line, for every function in your program.

Don't over think making your prototypes. Prototypes are simple copy+paste+add a semi-colon, operations.

It's a 10 second no-brainer, once you get to know them.