Array Search Question

[kpma]

Just got an assignment recently and need help with two questions from it.

Write a function, arraysearch, that searches through a sorted array of C
strings for a specified string, using the following function definition:

int arraysearch(char** array, int arraySize, char* searchString);

The function should return the index of the matching element in the
array, or the value 0 if the search string cannot be found.

The parameters are as follows:
Parameter Description
array Sorted array of C strings
arraySize Number of elements in the array
searchString C string being searched

Assumptions/Constraints

The strings in the array are sorted in ASCII alphabetical order.

The array and each of the elements of the array between 0 and
arraySize-1 are valid pointers.

The array may potentially contain a large number of elements, and the
function should be optimized for speed.

The array will not contain any duplicate elements.

Examples
char* array[5] = {"five", "four", "one", "three", "two"};

arraysearch(array, 5, "two") returns 5

arraysearch(array, 5, "six") returns 0

Should I be using string compare? or char compare?
First time taking programming class in University, need some help.

[kpma]

Actually nvm, solved it. :)

[NyhkoG1T]

The only problem I see is

char * arr[5] = {"five", "four", "one", "three", "two"};

the first "index" would be zero, the last being four. For example,

cout << arr[0]; // returns "five";
cout << arr[1]; // returns "four";
cout << arr[2]; // returns "one";
cout << arr[3]; // returns "three";
cout << arr[4]; // returns "two"; 

based on this fact, it would be better to return a value of "-1" because 0 could potentially be a matching element (i.e, searching for five, unsorted).

[vlad from moscow]

#include <iostream>
#include <algorithm>
#include <iterator>
#include <cstring>
 
size_t find_literal( const char **a, size_t n, const char *s )
{
    return( std::distance( a, 
                           std::find_if( a, a + n, 
                                         [=]( const char *t ) 
                                         { 
                                              return ( std::strcmp( t, s ) == 0 ); 
                                         } ) ) );
}
 
int main()
{
    const size_t N = 5;
    const char* array[N] = {"five", "four", "one", "three", "two"};
 
    size_t n = find_literal( array, N, "three" );
 
    if ( n != N )
    {
        std::cout << "literal \"" << "three" << "\" is found in position " << n << std::endl;
    }
}

[Cubbi]

Given

The strings in the array are sorted

and

the function should be optimized for speed.

it's likely that OP is asked to write a binary search, e.g.std::equal_range

[vlad from moscow]

@Cubbi

I did not take into account that the array is sorted. Then std::equal_range can be used.

#include <iostream>
#include <algorithm>
#include <iterator>
#include <cstring>
#include <utility>
 
size_t find_literal( const char **a, size_t n, const char *s )
{
    auto p = std::equal_range( a, a + n, s,
                               []( const char *s, const char *t ) 
                               { 
                                   return ( std::strcmp( s, t ) < 0 ); 
                               } );
    return ( p.first == p.second ? n : std::distance( a, p.first ) );    
}
 
int main()
{
    const size_t N = 5;
    const char* array[N] = {"five", "four", "one", "three", "two"};
 
    size_t n = find_literal( array, N, "three" );
 
    if ( n != N )
    {
        std::cout << "literal \"" << "three" << "\" is found in position " << n << std::endl;
    }
}