[c_code]

Hi
I need to do the following in c language:

Required to write a function that finds an integer in an array and returns
its corresponding index. The function must be called findNumber. It must have FOUR parameters:
 The first parameter is the array to be searched
 The second parameter is the integer to be found within the array
 The third parameter is the size of the array
 The fourth parameter is an integer that indicates whether the array is sorted. A value of 1
means the array is sorted; a value of zero means the array is not sorted.


_______________________________________

I am able to successfully create a function that will be able to search for an element in an array and successfully find it and display its position in the array , my problem is that I am not sure about the fourth parameter in the function ie: how to return the value of 1 or 0, as a function only allows the return of one value which will in my case be the corresponding index of the integer that is to be found.

Any help or advice will be really appreciated :tntworth:

Thanks :)

[Scorpions4ever]

I don't think you've understood the problem correctly. The fourth parameter indicates to the function whether the array is sorted or not.

The function can use this information to binary search the array, if it is told that the array is already sorted. Binary searching is a lot faster than linear searching.

[c_code]

Would I have to make use of pointers?

Where would i create the code to determine whether the function is sorted or not? 1. Within int main(void) or within my function "findNumber".

Thank you.. :tntworth:

[dwise1_aol]

No, you would not need to use pointers.

The function that calls this function would know whether the array is sorted or not. That's why it's giving that information to findNumber(). IOW, findNumber() does not need to make that determination, because that determination has already been made elsewhere and it's being given that information in the fourth argument.

[c_code]

Would you mind showing me an example?

Thanks.

[b49P23TIvg]

int findNumber(int*a, int target, size_t n, int sorted) {
  /* All parameters are input parameters */
  if (sorted) {
    /* implement O(log(n)) scorpion's search */
    /* I'd use bsearch */
  } else {
    /* implement O(n) search */
  }
  return the_index_or__1_or_class_chosen_unfound_value;
}

[c_code]

I have tried solving the problem according to the advice I have received from you guys. My program compiles but does not run correctly , if anyone can be kind enough to indicate to me where I have gone wrong in my coding , will really appreciate it so much!!!!! I really need to understand where I am going wrong in order to pass my C Language module for university :)

#include <stdio.h>
#define SIZE 10

size_t findNumber(const int a[],int searchKey,size_t size, int sort);



int main(void) {
	int a[ SIZE ] = {1,2,3,4,5,6,7,8,9,10};
	int key;
	int position;
	int sort;
	size_t i;
	int d_count=0;
	int a_count=0;

	for(i=9;i<SIZE;--i){
		if (a[i]< a[i-1])
		{
			d_count = d_count + 1;
		}
		else{
			if (a[i]>a[i-1]) {
				a_count = a_count + 1;
			}
		}
	}

	if (a_count==9 || d_count==9){
		sort=1;
	}
	else{
		sort=0;
	}


	printf("Please enter the integer that you are looking for: ");
	scanf_s("%d",&key);

	position=findNumber(a,key,SIZE,sort);

	printf("The ineteger is found in position: %d",position);

	return 0;
	

}


size_t findNumber(const int a[],int searchKey,size_t size, int sort){
	size_t index;
	int low = 0, high = size - 1, middle, found = 0, keyindex = -1; 

	if (sort==1){
		for (index = 0;index < size; ++index){
			if (a[index] == searchKey){
				return index;
			}
		}
	
	return -1;
	}

	else{
		if (sort==0){
			{  
				
                  while ( (low <= high) && (found == 0) )
                  { middle = (low + high) / 2;
                       if (searchKey == a[middle] )
                              { keyindex = middle;
                              found = 1;
                              }
                              else{
                              if (searchKey < a[middle] ){
                              high = middle - 1;
							  }
							  }
                               
                               if (searchKey > a[middle] ){
                               low = middle + 1;
							   
                               }
                               return keyindex;  }
                               }
	}

}







}

[clifford]

Originally Posted by c_code

My program compiles but does not run correctly

For starters you are performing the binary search on the unsorted array - the wrong way around.

You will get through this much faster and with far less external assistance if you us a debugger to step and understand how this code works (or doesn't as the case may be).

It will take you less than half an hour to learn debugger fundamentals such as stepping, watching, and breakpoints, but will save you many more hours thereafter. What development environment are you using?

Quite apart from getting the code working, if I were your tutor, I would mark you down for lack of comments, and multiple return points from a single function, and possibly code layout, though some of that may be due to the presentation on the forum of tabs as 8 spaces. If possible you should set your editor to indent with space rather than tab to avoid that.

[c_code]

Ok my bad I see that I have used the binary search for the unsorted array my code should be looking like this now since the correction: (but it is still not running correctly, Please indicate any problems that you see in my code, Thanks :))

#include <stdio.h>
#define SIZE 10

size_t findNumber(const int a[],int searchKey,size_t size, int sort);



int main(void) {
	int a[ SIZE ] = {1,2,3,4,5,6,7,8,9,10};
	int key;
	int position;
	int sort;
	size_t i;
	int d_count=0;
	int a_count=0;

 /* To loop through the specified array to determine whether integers within it are in descending/ascending order to determine whether it is sorted or not */
	for(i=9;i<SIZE;--i){
		if (a[i]< a[i-1])
		{
			d_count = d_count + 1;
		}
		else{
			if (a[i]>a[i-1]) {
				a_count = a_count + 1;
			}
		}
	}

	if (a_count==9 || d_count==9){
		sort=1;
	}
	else{
		sort=0;
	}


	printf("Please enter the integer that you are looking for: ");
	scanf_s("%d",&key);

	position=findNumber(a,key,SIZE,sort);

	printf("The ineteger is found in position: %d",position);

	return 0;
	

}


size_t findNumber(const int a[],int searchKey,size_t size, int sort){
	size_t index;
	int low = 0, high = size - 1, middle, found = 0, keyindex = -1; 

/* If the array is not sorted then the following linear search will be done on the array to find the position of an integer */
	if (sort==0){
		for (index = 0;index < size; ++index){
			if (a[index] == searchKey){
				return index;
			}
		}
	
	return -1;
	}

	else{
/*Binary search To determine the position in the array of an integer that is in an array which is sorted */
		if (sort==1){
			{  
				
                  while ( (low <= high) && (found == 0) )
                  { middle = (low + high) / 2;
                       if (searchKey == a[middle] )
                              { keyindex = middle;
                              found = 1;
                              }
                              else{
                              if (searchKey < a[middle] ){
                              high = middle - 1;
							  }
							  }
                               
                               if (searchKey > a[middle] ){
                               low = middle + 1;
							   
                               }
                               return keyindex;  }
                               }
	}

}

I am currently using Microsoft Visual c++ 2010 express to compile,build and run my programmes. I have also been using Linux but I still prefer MS Visual. What would you recommend?







}

[b49P23TIvg]

scanf_s("%d",&key);
scanf_s isn't a function that I'm aware of.

scanf("%d",&key);

I severely doubt that your program linked.



You decided if the list is ordered, but your binary search assumes ascending order. You are unlikely to discover this flaw with a debugger---you need appropriate test data.


While you're learning to use your debugger as clifford advises, I encourage you to also simplify the data. Use at most 3 integers in your array `a'. You'll have a more pleasant experience.


Stick with unix. Learn emacs. (the links to xkcd)

[dwise1_aol]

First, a stylistic matter.

In findNumber, the general structure is:

    if (sort==1)
    {
        // perform sequential search
        // return the index if found or -1 if not found
    }
    else
    {
        if (sort==0) // extraneous and useless additional test
        {
            {  // additional level of indentation that is absolutely useless

                // perform bisection search

            }  // end of absolutely useless additional level of indentation
        }
    }

That test for (sort==0) is not needed as long as sort can only have one of two values. Basically sort is either true or false, which are indicated by non-zero and by zero respectively. This binary test would normally be rendered thus:

    if (sort)  // any non-zero value
    {
        // perform bisection search
    }
    else  // implicitly, if it's not non-zero, then it must be zero
    {
        // perform sequential search
    }

Now, if you do anticipate sort having other values so that you must explicitly test for 1 and 0, then use the else-if construct. This way, you can create a long chain of else-if's for any number of conditions while leaving one final else to catch all cases that you didn't test for; eg:

    if (sort==1) 
    {
        // perform bisection search
    }
    else if (sort == 0) 
    {
        // perform sequential search
    }
    else
    {
        // deal with all other possible values of sort
    }

Of course, if that long chain of else-if's only test for different values of sort, then you should replace it with a switch construct; eg:

    switch(sort)
    {
        case 0:
            // handle case of sort == 0
            break;
        case 1:
            // handle case of sort == 1
            break;
        case 2:
            // handle case of sort == 2
            break;
        default:
            // handle all other cases
    }

You need to be more consistent with your indenting style. Place all braces out front instead of hiding them at the ends of lines. Indeed you mixed styles so that you confused yourself about where the braces were. Look at how you indented that function and then look at a more consistent style and your extraneous braces will jump out at you (but I commented them nonetheless):

size_t findNumber(const int a[],int searchKey,size_t size, int sort)
{
    size_t index;
    int low = 0, high = size - 1, middle, found = 0, keyindex = -1; 

    if (sort==1)
    {
        for (index = 0;index < size; ++index)
        {
            if (a[index] == searchKey)
            {
                return index;
            }
        }
    
        return -1;
    }

    else
    {
        if (sort==0)
        {
            {  // additional level of indentation that is absolutely useless
                while ( (low <= high) && (found == 0) )
                { 
                    middle = (low + high) / 2;
                    if (searchKey == a[middle] )
                    { 
                        keyindex = middle;
                        found = 1;
                    }
                    else
                    {
                        if (searchKey < a[middle] )
                        {
                            high = middle - 1;
                        }
                    }
                               
                    if (searchKey > a[middle] )
                    {
                        low = middle + 1;
                    }
                    return keyindex;  
                } // end while
            } // end extraneous and useless indentation level
        } // end if 
    } // end else
} // end findNumber

Commenting the close braces can be helpful, especially when there are a lot of them and if matching open and close braces cannot be seen on the screen together. Also, most editors have some way to match up braces, brackets, and parentheses; consult your editor's help file for details.

Originally Posted by c_code

My program compiles but does not run correctly

What makes you think that it doesn't run correctly?

IOW, why keep the symptoms a secret? Why don't you offer a short description of what you expect and what it gives you instead? That would help us greatly to help you, which is in your interest.

Look at the code in findNumber. If the array is sorted, then main sets sort to 1 and if the array is not sorted then main sets sort to 0. But in findNumber, if sort == 1 then you do the search for an unsorted array and if sort == 0 then you do the search of a sorted array. I think you have something switched around there.

Another stylistic point:
d_count = d_count + 1;
That is correct and is also the only way you can do that in most non-C-ish languages. But a C programmer would not write it that way. Instead, we have this construction:
d_count += 1;
It means the same thing, but it's more concise. Also, you can substitute any operator for '+' and you can substitute any value or expression for 1. However, that is still not the way that a C programmer would add one to d_count, AKA "increment d_count". Instead, he would write this:
d_count++;
or he could write
++d_count;
In a single statement, pre- or post-incrementing works the same, but if you use it in an expression then which one you choose would make a difference.

[dwise1_aol]

Originally Posted by b49P23TIvg

scanf_s("%d",&key);
scanf_s isn't a function that I'm aware of.

scanf("%d",&key);

I severely doubt that your program linked.

No, it would link. There is a set of functions including sprintf that Microsoft deems to be "unsafe", so it offers "safe" versions of those functions that it tries to force you to use. As I recall, they all take an extra argument which is the maximum size of the string they're stuffing -- I'm sure that scanf_s only exists because of the "%s" format. If you search through the help file you can find a macro that you can define to keep Visual Studio from complaining when you use the "unsafe" functions.

[c_code]

Thanks for all the input!
I have tried to alter the structure of my code to make it more easier to understand and follow:

#include <stdio.h>
#define SIZE 10

size_t findNumber(const int a[],int searchKey,size_t size, int sort);



int main(void) {
	int a[ SIZE ] = {1,2,3,4,5,6,7,8,9,10};
	int key;
	int position;
	int sort;
	size_t i;
	int d_count=0;
	int a_count=0;
	
	/* To determine whether the integers in the array are in ascending/descending order , to determine whether the array is sorted or not */
	for(i=9;i<SIZE;--i){                    
		if (a[i]< a[i-1])
		{
			d_count = d_count + 1;
		}
		else{
			if (a[i]>a[i-1]) {
				a_count = a_count + 1;
			}
		}
	}

	if (a_count==9 || d_count==9){
		sort=1; /*Indicates that array is sorted */
	}
	else{
		sort=0; /*Indicates that array is not sorted */
	}


	printf("Please enter the integer that you are looking for: ");
	scanf_s("%d",&key);

	position=findNumber(a,key,SIZE,sort);

	printf("The ineteger is found in position: %d",position);


	return 0;
	
}

/* Defining the function that will search for an integer in an array and return its position */
size_t findNumber(const int a[],int searchKey,size_t size, int sort){
	size_t low = 0, high = size - 1, middle, index=-1;
	int found=0;

	if (sort==1) /*Performs a binary search on the sorted array */
	{
		while ( (low <= high) && (found == 0) )
		{
			middle = (low + high) / 2;
			if (searchKey == a[middle] )
			{
				index = middle;
				return index;
				found = 1;
			}
			else
			{
				if (searchKey < a[middle] )
				{
                      high = middle - 1;
				}
				else
				{
					 low = middle + 1;
			    }
			}
		}
		
		return index;
	}
	
              
	else /* Performs a linear search on the unsorted array */
	{
		for (index = 0;index < size; ++index){
			if (a[index] == searchKey){
				return index;
			}
		}

}
}

The code looks perfect to me... it compiles , runs , but does not produce all the desired outcomes. The only error message the debugger gives me is :
" 1>c:\users\mo\documents\visual studio 2010\projects\prac5task1.c\prac5task1.c\prac5task1.c(92): warning C4715: 'findNumber' : not all control paths return a value"

Im not too sure what that means...

Any help is appreciated , you can try running my code using your own compilers/debuggers to see what is wrong and advice me.

Thanks once again :)

P.S: //my code needs to do the following:

Required to write a function that finds an integer in an array and returns
its corresponding index. The function must be called findNumber. It must have FOUR parameters:
 The first parameter is the array to be searched
 The second parameter is the integer to be found within the array
 The third parameter is the size of the array
 The fourth parameter is an integer that indicates whether the array is sorted. A value of 1
means the array is sorted; a value of zero means the array is not sorted.

[RobertWoges]

Originally Posted by c_code

Would I have to make use of pointers?

Where would i create the code to determine whether the function is sorted or not? 1. Within int main(void) or within my function "findNumber".

Thank you.. :tntworth:

No ,Dont use pointers.The function has already been determined .

[b49P23TIvg]

This is easier to follow:

#include <stdio.h>
#define SIZE 10

int a[ SIZE ] = {1,2,3,4,5,6,7,8,9,10};

int
  findNumber(int*a,int searchKey,size_t size, int sort),
  ordered(int*a,size_t n),
  linear_search(int*a, int searchKey, size_t size),
  binary_search(int*a, int searchKey, size_t size);


int main(void) {
  /*
     given an hard coded list that you cannot see,
     search for an integer in that list and report its
     index or -1 if unfound.
   */
  int key, sorted;
  fputs("Please enter the integer that you are looking for: ", stdout);
  sorted = ordered(a, SIZE);
  scanf("%d",&key);
  position=findNumber(a,key,SIZE,sorted);
  if (position < 0)
    puts("your key is not in the list");
  else
    printf("The integer is found in position: %d",position);
  return 0;
}


/* search for an integer in array and return its position, or -1 if unfound */
int findNumber(const int a[],int searchKey,size_t size, int sort) {
  int index;
  if (0 == sort)
    index = linear_search(a, searchKey, size);
  else if (1 == sort)
    index = binary_search(a, searchKey, size);
  else {		     /* use binary search with negated data */
    int i;
    for (i = 0; i < size; ++i)
      a[i] *= -1;
    index = binary_search(a, searchKey, size);
    for (i = 0; i < size; ++i)	/* restore */
      a[i] *= -1;
  }
  return index;
}


int ordered(int*a,size_t n) {
  /*
    examine a[0]...a[n-1]
    returns -1 if it is sorted descending
    returns 1 if ascending
    returns 0 if unsorted
  */

  /* your code here */

  return answer;
}


int linear_search(int*a, int searchKey, size_t size) {
  /* your linear search here */
  return index;
}


int binary_search(int*a, int searchKey, size_t size) {
  /* your binary search here */
  return index;
}