educative.io

In the binarysearch sample codes: why return low -1 when low >0

Courses
,
#1

Hi, could you please help to explain? Thanks.
private static int binarySearch(int[] arr, int target) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
…
}
if (low > 0) {
return low - 1;
}
return low;
}

3 Likes
#2

I think it really should be dependent on the absolute value of the difference with X, since arr[low] and arr[high] are the closest.

#3

It is wrong, say for array {2,5} target =4, the code return index 0 to be the closest one.

1 Like
#4

When the code reach the line meaning that we couldn’t find X, so we have 2 cases here. The first is X smaller than first value of the input array, high value would be -1 and low is 0. The second is X greater than last value of the input array then high equals to array.length - 1 and low index would be array.length so low is out of bound that makes calculations outside the function using the returned low is wrong.

1 Like
#5

Hey there,

Not sure if you had the same doubt as I did, spent quite a while trying to figure out why not just use low.

So, the thing is, when the target is in range, but doesn’t exist, it doesn’t really matter which one you use, the +K/-K coverage will always cover the required number of returned numbers, because no matter you start with low or low - 1, the closes two numbers to pick will be those two, and we still cover +/-K to the left and right.

I guess another way to see this is that there won’t be a case if you start low - 1, you’ll miss someone on the right side if you were to start with low, because of the aforementioned reasons.

This combines with the fact that if the target is larger than the last number, we would need to use low - 1, because of the out of bound issue. So, we just use low - 1 to cover the whole situation.

Not sure if that was why you asked question, but I had the same question and saw yours here, just put my own answer here.

Peace.

2 Likes
#6

This is a correct and easy explanation. Thanks.

#7

Let’s look at when this condition would be triggered?
if low > 0
e.g When you can’t find the element in upper bound ie. low would end + 1.

if number is less than start of array low would be negative
if number is greater than last element of array low would high + 1;

You can actually replace the condition with if low === high + 1, it is equivalent of low > 0 actually.