0

I have a string array and I am performing a linear and binary search. I understand how the linear search works but for the binary I don't understand this part:

else if (array[mid]<value){
            
            low=mid+1;
        }
        else{
            high=mid-1;
        }

What & how is the comparison between 2 strings happening here: array[mid]<value ?

This is my full code:


#include <iostream>
#include <string.h>
using namespace std;
int linearSearch(string array[],string value);
int binarySearch(string array[],string value);

int main(int argc, const char * argv[]) {
    string array[] = {"apple","banana","ciku","durian","rambutan"};
    string value="banana";
    //using linear search
    int location = linearSearch(array, value);
    cout<<"Location of durian is in:"<<location<<endl;
    //using binary search
    int position = binarySearch(array, value);
    cout<<"Location of durian is in:"<<position<<endl;
    
    
    
}

int binarySearch(string array[],string value){
    int low=0;
    int high=5;
    while(low<=low){
        int mid=(low+high)/2;
        if(array[mid]==value){
            return mid;
        }
        else if (array[mid]<value){
            
            low=mid+1;
        }
        else{
            high=mid-1;
        }
    }
    return -1;
}
int linearSearch(string array[],string value){
    
    
    int arrayLength = 5;
    for(int i=0;i<arrayLength;i++){
        if(array[i]==value){
            
            return i;
            
        }
    }
    return -1;
}

noobaka
  • 37
  • 7
  • What is you problem? Do you not understand binary search or do you have a problem with the implementation? – gerum Aug 30 '21 at 07:17
  • I don't understand how a string can be greater than another. This part to be specific: ```array[mid] – noobaka Aug 30 '21 at 07:19
  • 3
    Than you should take a look at the comparision operator of the string class: https://en.cppreference.com/w/cpp/string/basic_string/operator_cmp – gerum Aug 30 '21 at 07:23
  • Understood! Thank you! – noobaka Aug 30 '21 at 07:26
  • `std::string` is using lexicographic comparison - https://www.inf.unibz.it/~calvanese/teaching/04-05-ip/lecture-notes/uni05/node19.html – Slava Aug 30 '21 at 07:36
  • @prehistoricpenguin that's totally not related to this question. – TYeung Aug 30 '21 at 08:21

0 Answers0