There may be overflow in the binary search function at page16

[woodpenker]

First I want to say this is an excellent job! Thank you for sharing this!
At page 16, for question 34. Find First and Last Position of Element in Sorted Array (Medium), the function lower_bound below
may have a bug:

int lower_bound(vector<int> &nums, int target) {
int l = 0, r = nums.size(), mid;
while (l < r) {
mid = (l + r) / 2; // Here, may be overflow when r = MAX_INT and l= MAX_INT/2
if (nums[mid] >= target) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}

mid = (l + r) / 2; This code may be overflow when r = MAX_INT and l= MAX_INT/2, you should use mid = (r-l)/2+l instead.

Also the same for the upper_bound function.

[changgyhub]

Thanks!

Honestly I really don't want to touch too much about edge cases like this. Will be updated in the next version.