和大多数例子不同的是,我这里用的是unsigned而非int
和大多数例子另一个更重要的不同是:
这个二分查找函数在查找失败时还兼有返回一个适当插入位置的任务
具体迷糊的地方见代码注释
代码: 全选
//二分搜索,0表示最小元素
//high等于最大可用下标
//本函数二分查找网址字符串
//bsr是二分查找结果
void
my_bsearch (unsigned low, unsigned high, bsrtype * const bsr)
{
//中间位置
unsigned mid;
//最低位置
unsigned const lowest = low;
//最高位置
unsigned const highest = high;
bsr->found_site = UINT_MAX;
bsr->new_site = UINT_MAX;
assert (high < UINT_MAX);
int my_compar_rsult = 0;
if (url_total == 0)
{
bsr->new_site = 0;
return;
}
while (low <= high)
{
mid = low + ((high - low) / 2U);
my_compar_rsult = my_compar (mid);
if (my_compar_rsult == 0)
{
bsr->found_site = mid;
bsr->new_site = mid;
return;
}
//子表为空则直接跳出循环
else if (low == high)
{ //该从这里跳出?
//这里跳出可以确定无错误,但是否多余的进行了一次比较?
break;
}
else if (my_compar_rsult < 0)
{
if (lowest == mid)
break;
high = mid - 1U;
}
else if (my_compar_rsult > 0)
{
if (highest == mid)
break;
low = mid + 1U;
}
//子表为空则直接跳出循环
if (low == high)
{ //该从这里跳出?这里跳出是否会漏掉一次应该进行的比较?
break;
}
}
//"已找到串"设置为空串
found_string = my_realloc (found_string, 0);
//判断新元素插入位置
if (my_compar_rsult < 0)
bsr->new_site = mid;
else
bsr->new_site = mid + 1U;
return;
}