Thread: 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.

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

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

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

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.