### Array Search Question

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.
Actually nvm, solved it. :)
closed account (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,

 ``12345`` ``````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).
 ``123456789101112131415161718192021222324252627`` ``````#include #include #include #include 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; } }``````
Last edited on
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`
 @Cubbi

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

 ``12345678910111213141516171819202122232425262728`` ``````#include #include #include #include #include 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; } }``````
Last edited on
Topic archived. No new replies allowed.