struct key *binsearch(char *word,struct key *tab,int n)
{
int cond;
struct key *low=&tab[0];
struct key *high=&tab[n];
struct key *mid;
while(low<high)
{
mid=low+(high-low)/2;
if((cond=strcmp(word,mid->word))<0)
high=mid; //这里为什么不是mid-1
else if(cond>0)
low=mid+1;
else
return mid;
}
return NULL;
}
K&R书上的一个例题，在这里卡壳了 |
|
| 8分 | |
| 6分 |
从mid=low+(high-low)/2;可以看出这是一个前闭后开区间，即[low,hight), 如果要调整为mid-1，需要前后闭区间即[low,high],那么个数就是high-low+1了
|
| 6分 |
先
http://www.microsoft.com/visualstudio/chs/downloads#d-2010-express 点开Visual C++ 2010 Express下面的语言选‘简体中文’，再点立即安装 再参考C:\Program Files\Microsoft Visual Studio 10.0\VC\crt\src\bsearch.c /***
*bsearch.c - do a binary search
*
* Copyright (c) Microsoft Corporation. All rights reserved.
*
*Purpose:
* defines bsearch() - do a binary search an an array
*
*******************************************************************************/
#include <cruntime.h>
#include <stdlib.h>
#include <search.h>
#include <internal.h>
#if defined (_M_CEE)
#define __fileDECL __clrcall
#else /* defined (_M_CEE) */
#define __fileDECL __cdecl
#endif /* defined (_M_CEE) */
/***
*char *bsearch() - do a binary search on an array
*
*Purpose:
* Does a binary search of a sorted array for a key.
*
*Entry:
* const char *key - key to search for
* const char *base - base of sorted array to search
* unsigned int num - number of elements in array
* unsigned int width - number of bytes per element
* int (*compare)() - pointer to function that compares two array
* elements, returning neg when #1 < #2, pos when #1 > #2, and
* 0 when they are equal. Function is passed pointers to two
* array elements.
*
*Exit:
* if key is found:
* returns pointer to occurrence of key in array
* if key is not found:
* returns NULL
*
*Exceptions:
* Input parameters are validated. Refer to the validation section of the function.
*
*******************************************************************************/
#ifdef __USE_CONTEXT
#define __COMPARE(context, p1, p2) (*compare)(context, p1, p2)
#else /* __USE_CONTEXT */
#define __COMPARE(context, p1, p2) (*compare)(p1, p2)
#endif /* __USE_CONTEXT */
#if !defined (_M_CEE)
_CRTIMP
#endif /* !defined (_M_CEE) */
SECURITYSAFECRITICAL_ATTRIBUTE
#ifdef __USE_CONTEXT
void * __fileDECL bsearch_s (
REG4 const void *key,
const void *base,
size_t num,
size_t width,
int (__fileDECL *compare)(void *, const void *, const void *),
void *context
)
#else /* __USE_CONTEXT */
void * __fileDECL bsearch (
REG4 const void *key,
const void *base,
size_t num,
size_t width,
int (__fileDECL *compare)(const void *, const void *)
)
#endif /* __USE_CONTEXT */
{
REG1 char *lo = (char *)base;
REG2 char *hi = (char *)base + (num - 1) * width;
REG3 char *mid;
size_t half;
int result;
/* validation section */
_VALIDATE_RETURN(base != NULL || num == 0, EINVAL, NULL);
_VALIDATE_RETURN(width > 0, EINVAL, NULL);
_VALIDATE_RETURN(compare != NULL, EINVAL, NULL);
/*
We allow a NULL key here because it breaks some older code and because we do not dereference
this ourselves so we can""t be sure that it""s a problem for the comparison function
*/
while (lo <= hi)
{
if ((half = num / 2) != 0)
{
mid = lo + (num & 1 ? half : (half - 1)) * width;
if (!(result = __COMPARE(context, key, mid)))
return(mid);
else if (result < 0)
{
hi = mid - width;
num = num & 1 ? half : half-1;
}
else
{
lo = mid + width;
num = half;
}
}
else if (num)
return (__COMPARE(context, key, lo) ? NULL : lo);
else
break;
}
return NULL;
}
#undef __fileDECL
#undef __COMPARE
|
CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明有个结构体数组二分查找法，没想通 求解！
