yummyyenni - 2 months ago 12x

Java Question

Assume integer keys with sorted keys array:

`int[] keys = {10,20,30,40,50,60,70};`

`lo = 0`

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

Answer

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.

Source (Stackoverflow)

Comments