C语言二分查找迷糊了,该从哪里跳出循环?

科学之子 · **发表于 :** 2016-02-14 5:05

C语言二分查找迷糊了,该从哪里跳出循环?
和大多数例子不同的是,我这里用的是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;
}

astolia · **发表于 :** 2016-02-19 13:24

第一处：后面多余的比较一大堆，何必在乎这一处
第二处：会。如在{0,1}中查找2

科学之子 · **发表于 :** 2016-02-19 17:18

astolia 写道:

第一处：后面多余的比较一大堆，何必在乎这一处
第二处：会。如在{0,1}中查找2

第一处后面的比较真的是"多余"?

代码:

my_compar_rsult = my_compar (mid);

使用my_compar_rsult比较只是在内存中比较变量,但是如果进入到下一轮循环,就需要调用my_compar (mid)这个访问外存的函数来获取文件中的字符串比较信息
my_compar (mid)实际上是比较用户输入的字符串和索引中的第mid个字符串
因为用户输入的字符串被声明为全局标识符,所以没有出现在本段代码中.

astolia · **发表于 :** 2016-02-20 14:03

科学之子写道:

第一处后面的比较真的是"多余"?

我就举一个，你说判断 my_compar_rsult > 0 是不是多余？

C语言二分查找迷糊了,该从哪里跳出循环?

在线用户