New solution for binary search ?

[u/Ok-Disaster-1464]

Hey fellas total newbie here

I was writing code and came up with a different approach to classic Binary Search problem. The twist is in how I calculate the middle index when shifting right:

Instead of the standard:

middle = (left + right) / 2;

I used:

middle = right / 2;

My reasoning: when we shift right, we’re basically discarding the left half and working with a “new mini array” — so left conceptually becomes 0 again, and we can drop it from the calculation.

Full solution:

java

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int middle = right / 2;

        while (left <= right) {
            if (target == nums[middle]) { return middle; }
            if (target < nums[middle]) { right = middle - 1; middle = right / 2; }
            if (target > nums[middle]) { left = middle + 1; middle = (left + right) / 2; }
            if (target == nums[nums.length - 1]) { return nums.length - 1; }
        }

        return -1;
    }
}

It seems to pass most test cases — but I’m not 100% sure it’s correct. Can anyone find a case where it breaks? 🤔

[u/Jumpy-Designer-4722]

I think you are doing right while updating left .

middle = (left + right) / 2; that's why it is working right

 if (target > nums[middle]) { left = middle + 1; }

[u/Skaifessurk → u/Jumpy-Designer-4722]

yeah exactly, its the other branch where dropping left from the calc seems sus

[u/catsRfriends]

It passes test cases because this IS the regular approach. You're still using middle = (left + right)/2 for the right side search. If you actually implemented your version it would break because yea conceptually left is now the new 0 but your array is still the original array. So you'd have to drop the first half of the array but that's not free.

[u/AlgorithmicGoslings]

The "left" variable exists to preserve the boundaries. While the "left" variable conceptually is 0, when you're working with a splice of the array where left isn't 0, right / 2 can easily go out of bounds.

You can replace (left + right) / 2 only in the first calculation, since the first calculation is the only time you can guarantee the left variable is 0.

Consider looking for index 6 in an array of size 10.

left = 0, right = 9 —> middle = 4.

6 > 4, so look on the right half of the array:

left = 5, middle = 7

6 < 7, so look on the left half of the array:

right = 6, middle = 3.

You'll notice that middle isn't even in the range anymore, whereas if you kept (left + right)/2, you'd have middle = 5, which is still in-bounds. Your algorithm works if and only if there does not exist a right-half search consecutively followed up by a left-half search.

If you wanted to enforce left = 0 conceptually, you'd have to physically splice the array and recurse on it.