Page 1 of 2 12 Last
  • Jump to page:
    #1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2013
    Posts
    11
    Rep Power
    0

    Array Function Problem!


    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 :)
  2. #2
  3. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,624
    Rep Power
    4247
    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.
    Up the Irons
    What Would Jimi Do? Smash amps. Burn guitar. Take the groupies home.
    "Death Before Dishonour, my Friends!!" - Bruce D ickinson, Iron Maiden Aug 20, 2005 @ OzzFest
    Down with Sharon Osbourne

    "I wouldn't hire a butcher to fix my car. I also wouldn't hire a marketing firm to build my website." - Nilpo
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2013
    Posts
    11
    Rep Power
    0
    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:
  6. #4
  7. Contributing User
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2003
    Location
    USA
    Posts
    7,154
    Rep Power
    2222
    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.
  8. #5
  9. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2013
    Posts
    11
    Rep Power
    0
    Would you mind showing me an example?

    Thanks.
  10. #6
  11. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,850
    Rep Power
    481
    Code:
    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;
    }
    [code]Code tags[/code] are essential for python code and Makefiles!
  12. #7
  13. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2013
    Posts
    11
    Rep Power
    0
    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 :)

    Code:
    #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;  }
                                   }
    	}
    
    }
    
    
    
    
    
    
    
    }
  14. #8
  15. Contributing User

    Join Date
    Aug 2003
    Location
    UK
    Posts
    5,109
    Rep Power
    1803
    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.
    Last edited by clifford; March 26th, 2013 at 03:22 PM.
  16. #9
  17. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2013
    Posts
    11
    Rep Power
    0
    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 :))
    Code:
    #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?







    }
  18. #10
  19. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,850
    Rep Power
    481
    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)
    Last edited by b49P23TIvg; March 26th, 2013 at 04:03 PM.
    [code]Code tags[/code] are essential for python code and Makefiles!
  20. #11
  21. Contributing User
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2003
    Location
    USA
    Posts
    7,154
    Rep Power
    2222
    First, a stylistic matter.

    In findNumber, the general structure is:
    Code:
        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:
    Code:
        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:
    Code:
        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:
    Code:
        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):
    Code:
    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.
    Last edited by dwise1_aol; March 26th, 2013 at 04:38 PM.
  22. #12
  23. Contributing User
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2003
    Location
    USA
    Posts
    7,154
    Rep Power
    2222
    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.

    Comments on this post

    • b49P23TIvg agrees : Ah, thank you.
  24. #13
  25. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2013
    Posts
    11
    Rep Power
    0
    Thanks for all the input!
    I have tried to alter the structure of my code to make it more easier to understand and follow:

    Code:
    #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.
  26. #14
  27. No Profile Picture
    Banned
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2013
    Location
    New York
    Posts
    28
    Rep Power
    0
    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 .
  28. #15
  29. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,850
    Rep Power
    481
    This is easier to follow:
    Code:
    #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;
    }

    Comments on this post

    • c_code agrees : Looks like a feasible contruct!
    [code]Code tags[/code] are essential for python code and Makefiles!
Page 1 of 2 12 Last
  • Jump to page:

IMN logo majestic logo threadwatch logo seochat tools logo