0

在我用一种未命名的语言编写的程序中，我有一个宽度未知的文本块，而我所知道的只是该文本块的最大宽度。鉴于此信息，我需要找出此文本可能的最小宽度（假设我不能使用字符/字形或字符数的度量）。到目前为止，我只有一个蛮力解决方案，如下所示：

for (int i = .1; i < maxTextWidth; i += .1)
{
       if (textFitsInGivenWidth(text, i))
       {
             textWidth = i;
             break;
       }
}

我想尽可能地尝试和优化它。我的第一个想法是使用二进制搜索，但我无法以正确的方式实现它（并且不确定它是否可能）。有没有人对我可以在这里做些什么以仅使用我在上述解决方案中给出的内容来改善运行时间有任何建议？

4

1 回答 1

2

二进制搜索确实是答案。

http://en.wikipedia.org/wiki/Binary_search_algorithm

对于整数二进制搜索，它可以是：

minW=0, maxW=maxTextWidth
while(minW<=maxW){

  mid=(minW+maxW)/2;
  if (textFitsInGivenWidth(text, mid)){
    maxW=mid-1;
  }else{
    minW=mid+1;
  }
}
textWidth=minW

这个想法是，如果你有textFitsInGivenWidth(text, mid) == True，

那么你必须textFitsInGivenWidth(text, i) == True为所有i>=mid，

如果它是假的，那么你就拥有textFitsInGivenWidth(text, i) == False了i<=mid

所以每次我们检查要检查的区间的中间，并将区间减半。时间为 O(logN)，其中 N=maxTextWidth

更新：对于浮动支持，请参见下面的示例：

float minW=0, maxW=maxTextWidth
while(1){
  if (maxW-minW<0.05)
    break;
  float mid=(minW+maxW)/2;
  if (textFitsInGivenWidth(text, mid)){
    maxW=mid;
  }else{
    minW=mid;
  }
}

textWidth=minW

要获得 0.1 的精度，只需将最后一行更改为：

textWidth=int(minW*10)/10.0
于 2012-08-03T07:34:14.443 回答