В статьеhttp://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearchАвтор обсуждает бинарный поиск. Он делает различие между поиском наименьшего значения, где что-то верно, и наивысшего значения, где что-то ложно. Разыскиваемый массив выглядит примерно так:

ложный ложный ложный истинный истинный

Мне любопытно, почему эти два случая различны. Почему вы не можете просто найти самое низкое значение, которое является истинным, а затем вычесть одно, чтобы найти самое высокое значение, которое является ложным?

Edit2: хорошо, так что я понимаю нижнюю или верхнюю границу. Теперь я пытаюсь понять, при поиске наименьшего целого числа, большего или равного запросу, почему мы не можем просто изменитьif(mid>query) вif(mid>=query) и сделать это сделать ниже, а не верхнюю границу.

Редактировать: вот что говорится в статье:

«Теперь мы наконец-то добрались до кода, который реализует бинарный поиск, как описано в этом и предыдущем разделе:

binary_search(lo, hi, p):
   while lo < hi:
      mid = lo + (hi-lo)/2
      if p(mid) == true:
         hi = mid
      else:
         lo = mid+1

   if p(lo) == false:
      complain                // p(x) is false for all x in S!

   return lo         // lo is the least x for which p(x) is true

...

Если бы мы хотели найти последний x, для которого p (x) ложно, мы разработали (используя аналогичное объяснение, как указано выше) что-то вроде:

binary_search(lo, hi, p):
   while lo < hi:
      mid = lo + (hi-lo+1)/2    // note: division truncates
      if p(mid) == true:
         hi = mid-1
      else:
         lo = mid

   if p(lo) == true:
      complain                // p(x) is true for all x in S!

   return lo         // lo is the greatest x for which p(x) is false

«.