yummyyenni - 4 months ago 18
Java Question

# For binary search for keys in an array, what is the final value of lo or hi?

Assume integer keys with sorted keys array:

`int[] keys = {10,20,30,40,50,60,70};`
So initially in rank
`lo = 0`
and
`hi = 6`
.

For binary search for 30 in the keys array, would the final value of lo be 20, which is 1?

I just need to make sense of the logic.

Binary search would start like so:

``````lo = 0, hi = 6, mid = 3, numberInMid = 40
``````

As `30 < 40`, `hi = mid - 1 = 2`

Now,
`lo = 0, hi = 2, mid = 1, numberInMid = 20`

As `30 > 20`, `lo = mid + 1 = 2`

Finally,
`lo = 2, hi = 2, mid = 2, numberInMid = 30`

As `30 == 30`, loop exits and `ans = 30` If instead, you were searching for say 35 (I take this number since it fits with all above relational expressions), then:
As `35 > 30`, `lo = mid + 1 = 3`,
Since, `lo > hi`, loop exits and you are returned the default value of `ans`.
Eg:`ans = -1` if only positive integers are involved or instead, you may even use a `flag = false` which only switches to true when an `==` expression is hit.