Binary search an array of C-style strings

[Zettai Baka]

Part of my somewhat comprehensive project involves doing a binary insertion sort. I am trying to do just the binary search part right now. Here is just a relevant snippet of my code. Let's say I have an array of Records:

class Record
{
   public:
      char key[30];
};

Record file[100];  // sorted in ascending order 

I know the algorithm for a binary search -- divide the array, see if target is in the greater or lesser half, then divide that half, and repeat. I also know that I need to use strcmp() to compare strings.

But how do I find the "middle" of each half? If it's an array of sorted numbers, it would be easy because the middle is (low + high) / 2. But how do you find the "middle" of two STRINGS?

Thanks.

[Zettai Baka]

Maybe there's some weird way I can cast both strings to an integer, find the middle of those two integers, and then cast the result back to a string?

[helios]

Uh... You don't need to find the median, you just need to pick a pivot element to do a comparison. If the search value is lower than the pivot, search the lower segment, if it's higher, search the higher segment, otherwise, the search is over. It doesn't even need to be the middle one, it can be a random element.
To find the element in the middle, just do n/2. That's all you need to do.

[Zettai Baka]

Gah... I'm being stupid again... will try that. Thanks.

I think I have to use the middle element, because the specification requires the method to insert records in the file to be a binary insertion sort.

[helios]

As far as I know, there's no such thing. The insertion sort I know is this:
1. Insert element at the end.
2. If the size is <2, the element is at its final position.
3. Compare element with the previous.
4. If the previous element is greater, swap them, then go to step 3; otherwise, the element is at its final position.

[Zettai Baka]

I think what you're saying is the Insertion Sort. A binary insertion sort is a binary search, followed by the shifting of records to make room for the new element.

[Zettai Baka]

Regarding this snippet of my code, I'm getting a bunch of errors about invalid initializations and references and arguments regarding the function IndexFileBinarySearch :( Can someone advise just what I'm doing wrong here?

int IndexFileBinarySearch (indexRecord array[], int &low, int &high, char key[])
{
    	int mid;
	char temp[21];
	memset (temp, '\0', 21);
	strcpy (temp, key);

	if (low == 0 && high == 0)
		return 0;

   	mid = low + ((high - low) / 2);

	if (array[mid].key[0] == '\0')  // null result
	{
		printf ("\nSearch failed.\n");
		return -1;
	}

	printf ("\nYou want to search for key = %s. I am now at Key %d.\n", temp, mid);
	
	if (strcmp (temp, array[mid].key) == 0)
	{
		printf ("Comparison found.\n");
		printf ("\nKey is: %s (%d)", array[mid].key, mid);
		char c = getchar(); // to "step through" manually
    		return mid;
	}

    	else if (strcmp (temp, array[mid].key) > 0)
	{
		printf ("\nSearching upper");
		printf ("\nCurrent median key is: %s (%d)", array[mid].key, mid);
		char c = getchar(); // to "step through" manually
     	   	return IndexFileBinarySearch (array, mid + 1, high, temp);
		
	}
    	else if (strcmp (temp, array[mid].key) < 0)
	{
		printf ("\nSearching lower");
		printf ("\nCurrent median key is: %s (%d)", array[mid].key, mid);
		char c = getchar(); // to "step through" manually
      	  	return IndexFileBinarySearch (array, low, mid, temp);
	}
	else printf ("\nWah, it doesn't seem to be there.");
	
   	
}

[jsmith]

You cannot pass "mid + 1" as the actual parameter to IndexFileBinarySearch because the parameter is a reference.