/* 
 * Motif Tools Library, Version 2.0
 * $Id: BSearch.c,v 2.9 1994/07/04 03:03:50 david Exp $
 * 
 * Written by David Flanagan.
 * Copyright (c) 1992, 1993, 1994 by Dovetail Systems.
 * All Rights Reserved.  See the file COPYRIGHT for details.
 * This is not free software.  See the file SHAREWARE for details.
 * There is no warranty for this software.  See NO_WARRANTY for details.
 */
#include <Xmt/Xmt.h>

#if NeedFunctionPrototypes
int XmtBSearch(StringConst target, String *list, int num)
#else
int XmtBSearch(target, list, num)
StringConst target;
String *list;
int num;
#endif
{
    int half = num/2;
    int result;

    /* do a linear search if there aren't may keywords left */
    /* avoids the overhead of recursion */
    if (num <= 4) {
	for(num--; num >= 0; num--)
	    if (strcmp(target, list[num]) == 0) break;
	return num;
    }

    /* otherwise do a binary search */
    result = strcmp(target, list[half]);
    if (result == 0) return half;
    else if (result < 0)
	return XmtBSearch(target, list, half);
    else {
	result = XmtBSearch(target, &list[half+1], num-half-1);
	if (result != -1) result += half+1;
	return result;
    }
}