Using Merge Sort With Struct Array

[Bogeyman]

Hi, sorry for the delay in getting back, I had to finish up some other work.

I've had a look at binary search and I was wondering, is it searching for a value in an array or the index in an array?

For example, with this code here:

int binary_search(int a[], int low, int high, int searchkey)
{
    int mid = 0;

    while(low <= high)
    {
        mid = (low + high) / 2;

        if(searchkey < a[mid])
        {
            high = mid - 1;
        }
        else if(searchkey > a[mid])
        {
            low = mid + 1;
        }
        else
        {
            return searchkey;
        }
    }
}

Is it returning the index it found a matching value at, or the actual value?

[fg109]

The code is searching for a value in the array, and returns the value when it finds it. It doesn't make much sense; it should return the index of where it found the value instead.

int binary_search(int a[], int low, int high, int searchkey)
{
    int mid = 0;

    while(low <= high)
    {
        mid = (low + high) / 2;

        if(searchkey < a[mid])
        {
            high = mid - 1;
        }
        else if(searchkey > a[mid])
        {
            low = mid + 1;
        }
        else
        {
            return mid; //value found at index mid
        }
    }
    return -1; //value doesn't exist in search range
}

[Bogeyman]

I tried to change it to find a string in a struct array, but the index is always returned as 0.

Here's the code:

int binary_search(Record a[], int low, int high, char name[])
{
    int mid = 0;
    int ret_val = 0;

    while(low <= high)
    {
        mid = (low + high) / 2;

        ret_val = strcmp(a[mid].surname, name);

        if(ret_val < 0)
        {
            high = mid - 1;
        }
        else if(ret_val > 0)
        {
            low = mid + 1;
        }
        else
        {
            return mid;
        }
    }
}// end binary_search() 

[fg109]

ret_val = strcmp(a[mid].surname, name);

^ This is wrong. The return value of strcmp is less than 0 if the first string is less than the second string, and greater than zero if the first string is greater than the second string.

So this is basically the way you're using it:

        if(ret_val < 0) //a[mid].surname < name
        {
            high = mid - 1;
        }
        else if(ret_val > 0) //a[mid].surname > name
        {
            low = mid + 1;
        }
        else
        {
            return mid;
        }

I'm assuming that your compiler had the function automatically return 0 once it exits the loop, since you didn't specify a default return value.

[Bogeyman]

Yeah, when I added return -1 after the while loop, the output became -1. I guess that means the value is never found. How should I change it to make it work?

[fg109]

Read my last post again.

[Bogeyman]

I swapped the code in the if statements around and it's working now. Is that correct?

[Bogeyman]

The code works and I'm grateful for your help in getting it to work, so I'm marking this as solved. Thank you.