Implementation of binary search in online course looks incorrect. Am I crazy?
int binarySearch(int arr[], int x)
{
int l = 0;
int r = arr.length - 1;
do {
int m = l + (r - l) / 2;
if (arr[m] == x)
return m;
else if (arr[m] > x)
r = m;
else
l = m + 1;
} while (l < r)
return -1;
}
The only difference between my code and the code from the course is this is Java and his is in type script. Didn't want to re-write line for line from the video, so I found an example online and just updated it to look like his. Example just happened to be in Java.
Am I missing something here or does this fail on an array of two elements where the second element is target value "x." So for example lets say
arr = [5, 6]
x = 6
this will make l = 0, r = 1 and m = 0
arr[m] != 6 so the else statement will run making l = 1.
because l == 1 and r == 1, while(l < 1) now returns false so the binary search returns -1.
This youtuber is fairly big with about 500k subs, so i'd be really surprised to be the first one to notice such a simple error. This would effect all array that eventually narrow down to a selection of 2 elements that needs to grab the larger of the two to always return -1. I would just be very surprised if he never noticed or someone never brought it to his attention. So can someone please let me know if my logic is sound? Thank you!