Design a Character Searching Function, While Forced to Use strchr

Question

Background Information

I was recently approached by a friend who was given a homework problem to develop a searching algorithm. Before anyone asks, I did think of a solution! However, my solution is not what the teacher is asking for...

Anyway, this is an introductory C programming course where the students have been asked to write a search function called ch_search that is supposed to search an array of characters to determine how many times a specific character occurs. The constraints are what I don't understand...

Constraints:

1. The arguments are: array to search, character to search for, and length of the array being searched.
2. The function must use a for-loop.
3. The algorithm must use the strchr function.

Okay, so the first two constraints I can understand... but the 3rd constraint is what really gets me... I was initially thinking that we could just use a for-loop to iterate through the string from the beginning to the end, simply counting each instance of the character. When the student originally described the problem to me, I came up with (although incorrect) the solution:

Proposed Solution

int ch_search(char array_to_search[], char char_to_search_for, int array_size)
{
    int count = 0;

    for (int i = 0; i < array_size; i++)
    {
        // count each character instance
        if (array_to_search[i] == char_to_search_for)
        {
            // keep incrementing the count
            count++;
        }
    }

    return count;
}

Then I was told that I had to specifically use the character position function (and apparently it has to be strchr and not strrchr so we can't start at the end I guess?)... I just don't see how that wouldn't be overcomplicating this. I don't see how that would help at all, especially counting from the beginning... Even strrchr might make a little more sense to me. Thoughts?

Answer 1

strchr is a very convenient function to search for a char in a string.

Find and read more about strchr. This is my favorite function ever!

The C library function char *strchr(const char *str, int c) searches for the first occurrence of the character c (an unsigned char) in the string pointed to by the argument str.

Declaration

Following is the declaration for strchr() function.

char *strchr(const char *str, int c)

Parameters

• str − This is the C string to be scanned.

• c − This is the character to be searched in str.

Return value

Function returns a pointer to the first occurrence of the character c in the string str, or NULL if the character is not found.

Constraints:

1) The arguments are: array to search, character to search for, and length of the array being searched.

This constrain gives the length of the array to be searched. The given array has to contain '\0' at some point. However the length of search search can be shorter and specified by the search_length.

Following compact solution takes this under account.

int ch_search(char array_to_search[], char char_to_search_for, int search_length)
{
    int count = 0;
    for(char *p = array_to_search; ;p++)
    {
        p = strchr(p, char_to_search_for);
        if( p != NULL && (p - array_to_search < search_length) )
            count++;
        else
            break;
    }
    return count;
}

Or equivalent ch_search2:

#include<stdio.h>
#include<string.h>

int ch_search(char array_to_search[], char char_to_search_for, int search_length)
{
    int count = 0;
    for(char *p = array_to_search; ;p++)
    {
        p = strchr(p, char_to_search_for);
        if( p != NULL && (p - array_to_search < search_length) )
            count++;
        else
            break;
    }
    return count;
}

// Your original function:
int ch_search1(char array_to_search[], char char_to_search_for, int array_size)
{
    int count = 0;  
    for (int i = 0; i < array_size; i++){
        // count each character instance
        if (array_to_search[i] == char_to_search_for){
            count++;  // keep incrementing the count
        }
    }
    return count;
}

int ch_search2(char array_to_search[], char char_to_search_for, int array_size)
{
    int count = 0;
    char *p = array_to_search;

    for(;;)
    {
        p = strchr(p, char_to_search_for);
        if( p != NULL )
        {
            if (p - array_to_search >= array_size) // we reached beyond 
            {
                break;
            }
            else
            {
                count++;
                p++;
            }               
        }
        else
           break;  // char not found

    }
    return count;
}

int main(void)
{
    // the arr has to contain '\0' terminator but we can search within the specified length.
    char arr[]={'1','1','2','2','1','1','3','3','3','1','4','4', '1','1','!','1','\0','1'}; 
    char arr1[] = "zdxbab";

    printf("count %d count %d \n",ch_search(arr , '1', 12),ch_search2(arr , '1', 12));
    printf("count %d count %d \n",ch_search(arr1,'b',strlen(arr1)),ch_search2(arr1,'b',strlen(arr1)));

    return 0;
}

Output:

count 5 count 5                                                                                                                              
count 2 count 2

Answer 2

This sounds like your friend was given a trick question. The function gets an array of chars and the length of that array but is required to use strchr() even though that function only works on '\0' terminated strings (and there was not given any guaranty that the array is '\0' terminated).

You might thing that it would be fine to use strchr() on the array anyway and then compare the returned pointer to the given length of the array to check if it went past the end of the array. But there are two problems with that:

• If strchr() searches past the end of the array, then you already have Undefined Behavior before getting to the check. The program might have crashed before returning from strchr(), the returned pointer might be some total garbage or you might get a pointer to an address a bit further in memory than the end of the array.
• Even if the returned pointer is just to an address a bit further in memory than the end of the array, then there is the problem that comparing two pointers (or subtracting them to find the distance between the pointed addresses) is Undefined Behavior unless they're both pointing to parts of the same memory object (or one position past the end of the object). In this instance it means that checking if the returned pointer is within the bounds of the array is only defined behavior if the returned pointer is within the bounds of the array (or one past the end) making the check a bit useless.

The only solution to that is to make sure that strchr() is working with a '\0' terminated string. For example:

int ch_search(char array_to_search[], char char_to_search_for, int array_size)
{
    char *buffer = malloc(array_size + 1);
    // Add test here to check if malloc was succesful

    strncpy(buffer, array_to_search, array_size);
    buffer[array_size] = '\0';

    int count = 0;
    for (char *i = buffer; (i = strchr(i, char_to_search_for)) != NULL; i++) {
        count++;
    }
    free(buffer);
    return count;
}

Answer 3

I think the teacher wanted you to use strchr to navigate to the next occurrence of the char_to_search_for within a string:

int ch_search(char array_to_search[], char char_to_search_for, int array_size) {
    int count = 0;
    for (char *ptr = array_to_search ; ptr != &array_to_search[array_size] ; ptr++) {
        ptr = strchr(ptr, char_to_search_for);
        if (!ptr) {
            break; // Character is not found
        }
        count++;
    }
    return count;
}

Note that array_to_search must be null-terminated in order to be used together with strchr solution above.

Answer 4

It's true that having the length of the array and having to use a for loop, the most natural thing to do would be to iterate over every characters of the source array. But you can also loop over the result of strchr like this:

int ch_search(char haystack[], char needle, int size)
{
    int count = 0;

    char *found;

    for(; (found = strchr(haystack, needle)) != NULL; haystack = found + 1)
        count++;

    return count;
}

In this case you don't need the size of the array but the assignment doesn't say that you have to use it. Obviously this solution requires the source to be '\0'-terminated.