Find a string in a sorted array of strings that have some NULL strings, and
The array of strings is specified in sorted order, but there can be any number of null strings between them. I need to find a string in this array of strings. If the string is found, return its index, otherwise return -1. In the meantime, there is no need to know about it. ”
I wrote the code below using strcmp () which works for a string array without a NULL string. How do I extend it to work with arrays with null strings.
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int search(char *arr[], char *strtofind, int l, int r)
{
int mid , val;
if(l <= r)
{
mid = (l+r)/2;
val = strcmp(strtofind, arr[mid]);
if(val == 0)
return mid;
else if(val > 0)
{
return search(arr, strtofind,mid+1,r);
}
else
{
return search(arr, strtofind, l, mid-1);
}
}
return -1;
}
int main(int argc, char** argv)
{
int idx;
//char *arr[] = {"STR1", "STR2","STR3","STR4","STR5","STR6","STR7"}; // WORKS HERE
char *arr[] = {"STR1", "STR2","STR3",NULL,"STR4",NULL,"STR5"}; // NOT WORKS HERE
idx = search(arr, "STR4", 0, 6);
printf("Found at = %d\n", idx);
printf("Will is Everything.");
return (EXIT_SUCCESS);
}
source to share
Change the comparison code. A NULL
in arr[mid]
is essentially a "skip" of this element, so the comparison requires a linear search for the next or previous element.
To protect against worse conditions that really mess up your code, make sure that a subsequent search for the two halves of the list does not rescan the group of elements NULL
around mid
. Keep an eye NULL
on both ends of the list.
Worst case O(n*n)
that comes with a lot NULL
. Otherwise, performance O(n*ln2(n))
can be expected if NULL
rare.
Also, there is no need for a recursive call. See Comments
int search(const char *arr[], const char *strtofind, int l, int r)
while (l <= r) {
int mid = (l+r)/2;
int right_min = mid + 1;
while (arr[mid] == NULL) {
// If entire left side and mid are NULL ...
if (mid == 0) {
return search(arr, strtofind, right_min, r);
// or { l = right_min; continue; }
}
mid--;
}
int cmp = strcmp(strtofind, arr[mid]);
if (cmp == 0) {
return mid;
}
if(val > 0) {
return search(arr, strtofind, right_min, r);
// or { l = right_min; continue; }
}
int left_max = mid - 1;
return search(arr, strtofind, l, left_max);
// or { r = left_max; }
}
return -1;
}
Suggest: use const
.
An effective method exists when arr[]
everyone NULL
is on the same end.O(n*ln2(n))
source to share
Something like this will skip zeros. It resorts to linear search when it reaches zeros, but I can't think of a better way to do this.
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int search(char arr[][20], char *strtofind, int l, int r)
{
int mid , val, down = 1, start;
if(l <= r)
{
mid = (l+r)/2;
start = mid;
while(0 == arr[mid])
{
if(down)
{
if(mid >= l)
{
mid--;
}
else
{
down = 0;
mid = start;
}
}
else
{
if(mid <= r)
{
mid++;
}
else
{
return -1;
}
}
}
val = strcmp(strtofind, arr[mid]);
if(val == 0)
return mid;
else if(val > 0)
{
return search(arr, strtofind,mid+1,r);
}
else
{
return search(arr, strtofind, l, mid-1);
}
}
return -1;
}
int main(int argc, char** argv)
{
int idx;
char arr[][20] = {"STR1", "STR2","STR3","STR4"};
int num = sizeof(arr)/sizeof(arr[0]);
idx = search(arr, "STR2", 0, num-1);
if(-1 != idx)
{
printf("Found at = %d\n", idx);
}
else
{
printf("Not found");
}
return (EXIT_SUCCESS);
}
source to share