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

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.

Comments