CODEWITHSUNDEEP
c++arrays
user2277747
user2277747

Reputation: 89

recursive binarySearch with array of strings

My function works for the first 4 elements, but returns -1 for 12 and 14..even though there in the array. I've tried changing some of the if statements and using .compare but haven't had any luck. Any ideas? Thanks

/** Searches the array anArray[first] through anArray[last]
 for a given value by using a binary search.
 @pre 0 <= first, last <= SIZE - 1, where SIZE is the
 maximum size of the array, and anArray[first] <=
 anArray[first + 1] <= ... <= anArray[last].
 @post anArray is unchanged and either anArray[index] contains
 the given value or index == -1.
 @param anArray The array to search.
 @param first The low index to start searching from.
 @param last The high index to stop searching at.
 @param target The search key.
 @return Either index, such that anArray[index] == target, or -1.
 */
int binarySearch(const string anArray[], int first, int last, string target)
{
  int index;
  if (first > last)
    index = -1; // target not in original array
  else {
    // If target is in anArray,
    // anArray[first] <= target <= anArray[last]
    int mid = first + (last - first) / 2;
    if (anArray[mid] == target)
      index = mid; // target found at anArray[mid]
    else if (anArray[mid] > target)
      // Point X
      index = binarySearch(anArray, first, mid - 1, target);
    else
      // Point Y
      index = binarySearch(anArray, mid + 1, last, target);
  } // end if
  return index;
}

int main()
{
  const string v[6] = {"1","5","6","9","12","14"};

  int index;
  string searchItem = "12";

  cout << "Searching For: " << searchItem << endl;

  index = binarySearch(v, 0, 6, searchItem);

  cout << "Element found at index " << index << endl;

  system("pause");

  return 0;
}

Upvotes: 0

Views: 121

Answers (2)

franco______cc
franco______cc

Reputation: 1

Problem is that you can't compare full strings like you compare numbers (although you can do that with chars according to ascii value). You have two options, the first and simpler one is defining a function to compare strings, something like:

int compareStrings (string a, string b) { // -1: a>b, 0: a=b, 1: a<b
    if (a.length() == b.length()) {
        if (a == b) return 0;

        else for (int i = 0; i < a.length(); i++)
            if (a[i] < b[i]) return 1;
            else if (a[i] > b[i]) return -1;
    }

    else return (a.length() < b.length()? 1 : -1);
}

and then when you need to retrieve what string is bigger you could do:

int compResult = compareStrings (anArray[mid], target);
switch (compResult) {
    case -1:
        index = binarySearch(anArray, first, mid - 1, target); break;
    case 1:
        index = binarySearch(anArray, mid + 1, last, target); break;
}

The other one is creating a custom "wrapper" class for the strings such that you can override a comparing operator within it, but is a little bit more complicated, and the body of the functions would be pretty much the same, so I would suggest the former solution. But if you want to see how you could accomplish the latter of the solutions, here's a source: https://www.geeksforgeeks.org/c-program-to-compare-two-strings-using-operator-overloading/

Hope it helps man

Upvotes: 0

Slava
Slava

Reputation: 44258

Problem is the fact that for binary search to work your array has to be sorted with the same criteria you use with your binary search. Array you provided is not sorted. You sorted numbers, but you have strings and they compare differently - lexicographically. Which means that "12" comes before "5" and so on. So you either need to convert strings to numbers before you compare, use proper data type (probably int) or change order of elements in your array accordingly.

Note: your function "works" for the first four elements because for single digit numbers lexicographical and numerical compare is the same.

Note2: you also seem to pass wrong number as last, your doc clearly says "SIZE - 1", which is equal to 5. (your array has indexes from 0 to 5, not to 6)

Upvotes: 1

Related Questions