Searching a string inside a char array using Divide and Conquer

1.4k views Asked by At

Let's say that I have a struct array and each element has a name. Like:

struct something{
  char name[200];
}a[NMAX];

Given a new string (char array), i need to find the correct index for it using divide and conquer. Like:

char choice[200];
cin>>chioce;
int k=myFunction(choice);  // will return the index, 0 otherwise
                           // of course, could be more parameters
if( k )  
 cout<<k;

I don't know how to create that searching function (I tried, I know how D&C works but i'm still learning! ).

And no, i don't want to use strings !

This is what i tried:

int myFunction(char *choice, int l,int r)   // starting with l==0 && r==n-1
{
    int m;
    if(strcmp(a[m].name,choice)==0)
            return m;
    else{
            m=(l+r)/2;
            return myFunction(choice,l,m-1);
            return myFunction(choice,m+1,r);
    }
}
1

There are 1 answers

0
Sargam Modak On BEST ANSWER

This is my solution for your above problem. But i have modified a few things in your code.

#include<iostream>
using namespace std;

#define NMAX 10

struct something{
  char *name; //replaced with char pointer so that i can save values the way i have done
}a[NMAX];

int myFunction(char *choice, int l,int r)   // starting with l==0 && r==NMAX-1
{
    if(l>r) //return if l has become greater than r
        return -1;
    int m=(l+r)/2;

    if(strcmp(a[m].name,choice)==0)
            return m+1;
    else if(l==r) //returned -1 as the value has not matched and further recursion is of no use
                return -1;
    else{

            int left= myFunction(choice,l,m-1);//replaced return
            int right= myFunction(choice,m+1,r);//by saving values returned
            if(left!=-1)                      //so that i can check them,
                return left;                  //otherwise returning from here onlywould never allow second satatement to execute
            if(right!=-1)
                return right;
            else
                return -1;
    }
}

int main(){

a[0].name="abc";
a[1].name="a";
a[2].name="abcd";
a[3].name="abcf";
a[4].name="abcg";
a[5].name="abch";
a[6].name="abcj";
a[7].name="abck";
a[8].name="abcl";
a[9].name="abcr";
char choice[200];
cin>>choice;
int k=myFunction(choice,0,NMAX-1);  // will return the index, 0 otherwise
                           // of course, could be more parameters
if( k !=-1)
 cout<<k;
 else
    cout<<"Not found";
return 0;
}

Hope it will help.