Binary search string

[avi1109]

Hello, i'm stuck with a problem on binary search. I need to compare a string with an array of type string.
It is changing the position from which the string should be read but z compare is not successful.
here's my code.
Any help would be appreciated.
thanks in advance.

int n=500;
    string name;
    string element;
    cout<<"\nEnter institute name:";
    cin>>element;
    

int l,u,m, flag = 0;
l = 0; 
u = n-1;
while(l <= u) { 
        m =( (l+u)/2);
        cout<<"Searching at location"<< m<<endl;
        cout<<Institute[m]<<"HI"<<endl;
        if(element==Institute[m]) 
        {
    cout << "\nMatch found at " << i << endl;
	    flag =1;
        break; 
         }
     else 
         { 
            	if(Institute[m] < element)
                  l = m+1;  
              else
                  u = m-1; 
         }
     }
     if( flag == 0)
     cout<<"\nElement not found\n";

[mitrmkar]

>>It is changing the position from which the string should be read but z compare is not successful.

I don't quite understand that, but with regard to the search itself, you are quite close to a solution. However, in order for the binary search to work, the data (your Institute[] array) must be sorted. Maybe that's the basic problem with your attempt i.e. you are searching an unsorted array?

PS. Note also that the string comparison (element==Institute[m]) is case-sensitive i.e. "Abc" != "abc".

[avi1109]

>>It is changing the position from which the string should be read but z compare is not successful.

I meab that the binary search is working but i'm unable to compare the strings. i've already tried inbuilt functions like
element.compare( Institute[m]).
But it's not leading me to anywhere.
Thanks for helping

[hammerhead]

Hello, i'm stuck with a problem on binary search. I need to compare a string with an array of type string.
It is changing the position from which the string should be read but z compare is not successful.
here's my code.
Any help would be appreciated.
thanks in advance.

int n=500;
    string name;
    string element;
    cout<<"\nEnter institute name:";
    cin>>element;
    

int l,u,m, flag = 0;
l = 0; 
u = n-1;
while(l <= u) { 
        m =( (l+u)/2);
        cout<<"Searching at location"<< m<<endl;
        cout<<Institute[m]<<"HI"<<endl;
        if(element==Institute[m]) 
        {
    cout << "\nMatch found at " << i << endl;
	    flag =1;
        break; 
         }
     else 
         { 
            	if(Institute[m] < element)
                  l = m+1;  
              else
                  u = m-1; 
         }
     }
     if( flag == 0)
     cout<<"\nElement not found\n";

I am assuming that you have already declared and initialized the array Institute[n] as you have not displayed it in the code. If not then do it for all n=500 (i would suggest you try your code at a much lesser value first).

In line 17

cout << "\nMatch found at " << i << endl;

replace variable i with m or declare a variable i and equate it with m inside the loop.

Also remember that in binary search the array has to be in a sorted order. In this case the strings in Institute have to be arranged in alphabetical manner.

[Ancient Dragon]

you could resort to C's stricmp(), or for some compilers, comparenocase() to make case-insensive comparisons if( stricmp(element.c_str(),Institute[m].c_str()) == 0) There is also c++ std::transform() that you could use to convert the strings to either all upper or lower case before comparison, but its a lot more ugly to read and code.

[hammerhead]

Dosnt the '<' operator for strings compare in alphabetical order? I am using Dev c++ 4.9 and it worked for simple cases for me.

[Ancient Dragon]

>> Dosnt the '<' operator for strings compare in alphabetical order
Not in alphabetical order but in order by their ascii values. Strings can contain a lot of other things than letters of the alphabet. The string "alpha" is less than "beta" because 'a' < 'b' (the first letter of each word. And "#alpha" is < "alpha" because '#' has a lower ascii value than 'a'