C home help: searching arrays

Question

I am working on a problem when I am given a sorted array of integers, and I have to take the data from the user, find the input and return the first instance of this input (if it exists) and the number of times it appears.

I wrote a program with the following approach: I take input from the user. Then I use binary search to find the value. If it exists, I save the index as m . After that, I write two while . The first cycle checks the number of occurrences of the value to the left, and the second does the same, but to the right. For example, a binary search may search for 5, and it finds it. However, he lands on the third, i.e. {.....5,5,**5**,5....} . The first while will count two on the left, and the second, while the loop will count one on the right. Then I summarize them and return the total number of instances. If the input value does not exist, I skip the above code and just return -1.

In the body of the main function, I check the return value. If it is -1, I tell the user that the value was not found. If the return value => 0, I print the required information.

In any case, I wrote C code for the program, but I can not get it to work correctly. I get seg. error error, I don’t know what I am doing wrong though. In any case, any help would be appreciated. For a while I banged my head about this problem. It was interesting and difficult, and I think I have the right logic; but I can't get it to work correctly. Anyway, here is the code:

 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <stddef.h> /* function prototype */ int get_num_of_ints( const int* arr, size_t r, int N, size_t* f, size_t* count ); int main() { int i; int N; /* input variable */ int arr[]={1,1,2,3,4,4,4,4,5,5,6,7,7,7,7,8,9,9}; /* array of sorted integers */ size_t r = sizeof(arr[i])/sizeof(int); /* right bound */ size_t f; /* first match index */ size_t *fPtr; fPtr = &f; size_t count; /* total number of matches */ size_t *countPtr; countPtr = &count; printf( "\nPlease input the integer you would like to find.\n" ); scanf( "%d", &N ); int a = get_num_of_ints( arr, r, N, fPtr, countPtr ); if( a == -1) printf( "%d has not been found.\n", N ); else if(a >= 0){ printf( "The first index is %d.\n", f ); printf( "The total number of values is %d.\n", count ); } return 0; } /* function definition */ int get_num_of_ints( const int* arr, size_t r, int N, size_t* f, size_t* count ) { int l = 0; int m; int w=r; size_t *fPtr; size_t *countPtr; while(l <= r){ m = l +(r - l)/2; if(arr[m] < N) l = m+1; else if(arr[m] > N) r = m-1; else if(arr[m]==N) m=m; break; } if( l > r) m = -1; if( m >= 0 ){ int j = m-1; int L = 0; while(arr[j] == arr[m] && j >= 0){ L++; j--; } if( j>= 0 && L > 0 ) *fPtr=j; else *fPtr=m; int h = m + 1; int R = 0; while( arr[h]==arr[m] && h <= w ){ R++; h++; } *countPtr = (R + L + 1); return *fPtr; } else if( m==-1) return -1; } 

Answer 1

 while(arr[j] == arr[m] && j >= 0) 

Here you have to switch the order of the two conditions, or you try to read arr[-1] . The same goes for the second while loop.

Another problem is that r must start with 1 less than the size of the array, as arr[array_size] ends.

Edit:

The serious problem is that you write uninitialized pointers to countPtr and fPtr when you must write to *count and *f . This is probably the reason for segfault. This would be easy to spot in the debugger.

Answer 2

• Use variable names that mean something. You can find the problem right away.

• Run the program in the debugger and execute the code; you should see where things are not going so fast. (Hint, why is fPtr used in get_num_of_ints ? There are other errors, as others have pointed out).

Answer 3

Since you need the number of occurrences, you need to do a search on each element, right?

Why not simplify things and just do a linear scan? Here's some pseudo code:

 function get_num_of_ints(arr, n){ first_index = -1 count = 0 for(i = 0; i < length(arr); i++) if(x == n){ count++ if(first_index == -1) first_index = i } return count, first_index } 

Answer 4

I don’t have the C compiler on the computer I'm sitting in now, so I can’t test it, but I see that in the first loop of your function you say:

 else if(arr[m]==N) m=m; break; 

The break statement is outside of if in this case, so the while loop will only be executed once every time.

I do not know if this caused an error.

Answer 5

The segmentation error comes from get_num_of_ints () on lines 74, 77, and 87.

 if( j>= 0 && L > 0 ) *fPtr=j; else *fPtr=m; ... *countPtr = (R + L + 1); 

You have not assigned a memory address to the pointers, and thus you are using an arbitrary memory location on these lines.

There seems to be no real reason to use a pointer for these variables anyway. Try changing them from pointers to size_t to just variables of type size_t.

 size_t fPtr; size_t countPtr; 

Answer 6

In the get_num_of_ints () function, you use the fptr pointer without allocating memory for it.

Answer 7

Thanks to all the comments, I was able to find all the errors in my program and use the gdb debugger. In any case, I no longer have my segment. errors when starting the program; however, I have some kind of logical problem, because when I ask the user for input and say that the user type is 4, then the outputs for the # occurrence and location of the first entry are garbage values.

I get:

 Please input the integer you would like to find. 4 The first index is -1075300456. The total number of values is 12169204. 

This revolves around the question I had previously with the last two parameters in my function. At the bottom of the function definition, I want count to be the total number of entries found in the list.

 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <stddef.h> /* function prototype */ int get_num_of_ints( const int* arr, size_t r, int N, size_t f, size_t count ); int main() { int i; int N; /* input variable */ int arr[]={1,1,2,3,4,4,4,4,5,5,6,7,7,7,7,8,9,9}; /* array of sorted integers */ size_t r = sizeof(arr)/sizeof(arr[0]) - 1; /* right bound */ size_t f; /* first match index */ size_t count; /* total number of matches */ printf( "\nPlease input the integer you would like to find.\n" ); scanf( "%d", &N ); int a = get_num_of_ints( arr, r, N, f, count ); if( a == -1) printf( "%d has not been found.\n", N ); else if(a >= 0){ printf( "The first index is %d.\n", f ); printf( "The total number of values is %d.\n", count ); } return 0; } /* function definition */ int get_num_of_ints( const int* arr, size_t r, int N, size_t f, size_t count ) { int l = 0; int m; int w=r; while(l <= r){ m = l +(r - l)/2; if(arr[m] < N) l = m+1; else if(arr[m] > N) r = m-1; else if(arr[m]==N){ m=m; break; } } if( l > r) m = -1; if( m >= 0 ){ int j = m-1; int L = 0; while( j >= 0 && arr[j] == arr[m] ){ L++; j--; } if( j>= 0 && L > 0 ) f=j; else f=m; int h = m + 1; int R = 0; while( arr[h]==arr[m] && h <= w ){ R++; h++; } count = (R + L + 1); return f; } else if( m==-1) return -1; } 

Answer 8

• As pointed out by all countPtr and fPtr , memory must be allocated

  size_t * fPtr = malloc (sizeof (size_t));

• Before using it, make sure that you initialize "i" with some value.

• Compile the program (if you are on Linux) with # gcc -g -Wall <your c file name> -o arraysort

  Run the debugger, go through the code to find out valeues, I found some funny values ​​for r, arr [m],

  # gdb. / arraysort

  b run [check variables here]

NTN