0

I tried to return the right index of an array element with a recursive binary search algorithm, however it returns just the index of the portion taken into consideration.
For example, if the list is composed by the name "Grant", "Anthony" and "Samuel", the algorithm will return the value 0 if I search for "Samuel".

short binarySearch(person key, person list[], short n)
{
    size_t mid;
    if(n == 0)
        return -1;
    mid = (n-1)/2;
    if(strcmp(key.name, list[mid].name) == 0 && strcmp(key.surname, list[mid].surname) == 0)
        return mid;
    
    else if(strcmp(key.name, list[mid].name) < 0)
        return binarySearch(key, list, mid);
    else
        return binarySearch(key, list+mid+1, n-mid-1);
}

UPDATE:

I solved in this way (thanks to @mevets and @selbie):

int binarySearch(person key, person *list, size_t n)
{
    int cmp = 0, result;
    size_t mid;
    if(n == 0)
        return -1;
    mid = (n - 1) / 2;
    cmp = strcmp(key.name, list[mid].name);
    if(cmp == 0)
    {
        cmp = strcmp(key.surname, list[mid].surname);
        if(cmp == 0)
            return mid;
    }
    if(cmp < 0)
        return binarySearch(key, list, mid);
    result = binarySearch(key, list+mid+1, n-mid-1);
    if(result == -1)
        return -1;
    return 1 + mid + result;
}
Improve this question
2
  • One minor bug in your program - if two items in list have the same name property value, but different surname value, you could potentially recurse the wrong subarray. Consider the array [{"bob", "anderson"}, {"bob", "jones"}, {"bob, "zumuda"}]. And then you search for "bob anderson". Commented Dec 23, 2020 at 1:05
  • That of course assumes that your items are ordered by first name and surname as tie-breaker. If the items are ordered by surname, a similar bug still exists. I'll update my answer below to show the fix. Commented Dec 23, 2020 at 1:15

2 Answers 2

Reset to default
1

Instead of adjusting list and n (size of list), pass the start/end indices of the list.

Also, take note that your program has a minor bug when dealing with users with identical first names, but different last names

int binarySearch(const person* key, const person* list, int start, int end)
{
    // end is "1 past" the last valid index in list
    int cmp = 0;

    int mid = (start + end) / 2;

    if (start >= end)
    {
        return -1;  // list is empty or we've exceeded our bounds
    }

    // sorting on name, then surname as tiebreaker
    // if you need to sort on surname first, swap the two strcmp statements
    cmp = strcmp(key->name, list[mid].name);
    if (cmp == 0)
    {
        cmp = strcmp(key->surname, list[mid].surname);
        if (cmp == 0)
        {
            return mid;
        }
    }

    if (cmp < 0)
    {
        // recurse into the left side of the array
        return binarySearch(key, list, start, mid);
    }
    
    // recurse into the right side of the array
    return binarySearch(key, list, mid + 1, end);
}

And then as a shim for your existing function signature:

short binarySearch(person key, person list[], short n)
{
    return binarySearch(&key, list, 0, n);
}

Also, for efficiency, you should pass key by pointer rather than by value. list is already being passed as pointer.

Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

Thank you so much! So there's no way to do this with just the array size?
arrays don't have sizes in C. They are just pointers when passed to functions.
Yes I know, I mean the number of the elements of the array. By the way, thank you for the answer!
You could take mevets answer below and just check for -1 as return code before doing the mid+1 adjustment. I've given you a few other bug fixes as well.
Exactly. result = binarySearch(...); if (result == -1) return -1; return mid+1+result;
|
1

Change your last:

return binarySearch(key, list+mid+1, n-mid-1);

to:

return mid + 1 + binarySearch(key, list+mid+1, n-mid-1);
Improve this answer

6 Comments

NIce and sweet.
Why if I enter a not listed string sometimes it doesn't return -1? For example, if I enter "Name: j Surname: K" it returns the index which matches with the strings "John" and "Kennedy".
Right, not quite a solution. Often search routines will return the insertion point if the element isn't found, so i = binarySearch(key, list, n); if (i > 0 && strcmp(key.name, list[i].name) { i = -1; }
or look at rewriting it as per @selbie below
What should be the result of the strcmp? strcmp != 0?
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.