En el artículohttp://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearch, el autor analiza la búsqueda binaria. Hace una distinción entre encontrar el valor más bajo donde algo es verdadero y el valor más alto donde algo es falso. La matriz que se busca se parece a:

falso falso falso verdadero verdadero

Tengo curiosidad por saber por qué estos dos casos son diferentes. ¿Por qué no puedes simplemente encontrar el valor más bajo que es verdadero, luego restar uno para encontrar el valor más alto que es falso?

Edit2: Ok, entiendo el límite inferior vs superior. Ahora, me cuesta entender, cuando busco el número entero más pequeño mayor o igual a la consulta, por qué no podemos simplemente cambiar elif(mid>query) aif(mid>=query) y que se haga más bajo en lugar de límite superior.

Editar: Esto es lo que dice el artículo:

"Ahora finalmente llegamos al código que implementa la búsqueda binaria como se describe en esta y en la sección anterior:

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

...

Si quisiéramos encontrar la última x para la cual p (x) es falsa, idearíamos (usando una lógica similar a la anterior) algo como:

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

".