Sorting and Comparing strings without using string library functions

Question

The challenge: Given a sorted array of names (only first name) and a name X for which I need to find out how many times it is present in the array. Constraint: Only binary search is allowed.Also I cannot use any string library function. Sample Input:

3
abc
abc
pqr
pqr

output: 1(as pqr occurs just once in the array of strings/words).

Answer 1

1) Compare string without using string library: implement the string comparison function by yourself: compare the first characters of both strings, only if they are equal, compare the next characters, and so on.

2) Sorted array and binary search: Binary search is perfect for a sorted array. Let x be the query string.

Step 1: Use binary search to find x in the sorted array.

Step 2: If cannot found, return 0.

Step 3: If found, binary search for x in the left and right subarray. Record the result indexes.

Repeat step 3 (Note: smaller left, right sub-arrays in each loop), stop the search in left (or right) direction if cannot find x in left (or right) subarray. The previous found indexes of left and right gives the range of results.

Answer 2

There are plenty of questions on SO about how to compare strings in C, so I will just direct you to those questions and their answers. Basically, the solution is to compare the strings character by character until you either find a pair of characters that differ, or until you reach the end of both strings. Then compare the characters at the point you've reached, and return the result of that comparison.

As for using binary search to find the number of times a given target string occurs in a sorted array, probably the simplest efficient solution is to do two binary searches: one for the starting point and one for the end point of the range of array elements equal to the target. The distance from the starting point to the end point will then give the length of the range.

The following binary search routine will return the index of the last element in the array haystack that is less than the target needle (or -1, if there is no such element):

int find_last_less_than(int needle, int *haystack, int length) {
    int base = -1, step = length - base;

    // loop invariants:
    // 1. base == -1 || haystack[base] < needle
    // 2. base + step >= length || haystack[base + step] >= needle
    while (step > 1) {
        step = (step + 1) / 2;  // divide interval in half, rounding up
        int index = base + step;
        if (index < length && haystack[index] < needle) base += step;
    }
    return base;
}

Note that for simplicity (and to avoid just spoon-feeding you the entire solution) this code searches an array of integers rather than of strings, but I trust that you can figure out how to modify it as needed.

Hopefully, it should also be clear how to modify the search so that, instead of finding the last element less than the target, it will find the index of the last element less than or equal to the target. Subtracting the former from the latter will then yield the number of times the target occurs in the array.

Answer 3

Here is the code I wrote to perform the task:

enter code here
#include<stdio.h>
#include<stdlib.h>
int first(char *a[26],int low,int high,char *word,int n);
int last(char*a[26],int low,int high,char* word,int n);


int mycomp(char* a,char* b){

  int i = 0;
  while (a[i] == b[i] && a[i] != '\0')
   i++;
   if (a[i] > b[i])
      return 2;
   else if (a[i] < b[i])
     return -2;
   else
     return 0;



}

int main(){

int n,count=0;


scanf("%d",&n);
char dictionery[n][50];
char word[50];
  int i,j;
  for(i=0;i<n;i++)
      scanf("%s",dictionery[i]);

  scanf("%s",word);

 i = first(dictionery[n],0,n-1,word,n);

 if(i==-1)
  printf("No occurrances\n");

  else{
   j = last(dictionery[n],i,n-1,word,n);
   count = j-i+1;
   printf("%d\n",count);

  }

 return 0;
}

int first(char *a[26],int low,int high,char *word,int n){

 if(high >= low){
    int mid = (high+low)/2;
    int d = mycomp(word,a[mid-1]);
    int e = mycomp(word,a[mid]);
    if((mid==0 || d>0)&& e==0)
        return mid;

    else if(e>0)
       return first(*a[],mid+1,high,word,n);
    else
       return first(*a[],low,mid-1,word,n);




 }

 return -1;


}

int last(char* a[26],int low,int high,char* word,int n){

if(high>=low){
    int mid = (high+low)/2;
    int d = mycomp(word,a[mid+1]);
    int e = mycomp(word,a[mid]);

    if((mid==n-1 || d<0)&& e==0 )
       return mid;
    else if(e<0)
       return last(*a[],low,mid-1,word,n);
    else 
       return last(*a[],mid+1,high,word,n);

}
return -1;


}

Is this the most efficient way of performing the task?