9

9

In the article http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearch, the author discusses binary search. He makes a distinction between finding the lowest value where something is true, and the highest value where something is false. The array being searched looks something like:

false false false true true

I am curious as to why these two cases are different. Why can't you just find the lowest value which is true, then subtract one to find the highest value which is false?

Edit2: Ok, so I understand lower vs upper bound. Now, I am struggling to understand, when searching for the smallest integer greater than or equal to the query, why we can't just change the `if(mid>query)`

to `if(mid>=query)`

and have it do lower instead of upper bound.

Edit: Here is what the article stated:

"Now we finally get to the code which implements binary search as described in this and the previous section:

```
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
```

...

If we wanted to find the last x for which p(x) is false, we would devise (using a similar rationale as above) something like:

```
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
```

."

2Well, im assuming that binary search implies the set looks something like

false .... false true ... trueno matter what – John Targaryen – 2015-02-08T00:18:08.977The article im referring to implies that this is the case if we are performing binary search; i beleive thats also a necessity for binary search to even apply to the situation. – John Targaryen – 2015-02-08T00:27:46.843

@DietmarKühl sure, but couldnt you easily check that with like

`if(lo==0&&works(lo)==true)return false`

? – John Targaryen – 2015-02-08T00:29:30.830