The essence the template II is to get search space of 2 instead of 1, howover it does not work for me let's solve this problem.
the problem says
"givin an array of integers find 2 number such that if you add them togother you get a givin target if you find the 2 numbers find return the index of the first element"
Well if we use binary search defintly we will need search space of 2 here is a code built on top of the template II
class Solution {
public:
int search(vector<int>& nums, int target) {
if (nums.size() == 0)
return -1;
int left = 0, right = nums.size();
while (left < right) {
// Prevent (left + right) overflow
int mid = left + (right - left) / 2;
if (nums[mid] + nums[mid + 1] == target) {
return mid;
}
else if (nums[mid] + nums[mid + 1] < target) {
left = mid + 1;
}
else {
right = mid;
}
}
if (left < nums.size() - 1 && nums[left] + nums[left + 1] == target) {
return left;
}
return -1;
}
};
int main(void) {
Solution solution;
vector<int> nums = { 1, 2, 3, 4 };
// This will work fine
cout << solution.search(nums, 7) << endl;
// But this will through an error
cout << solution.search(nums, 9) << endl;
}this code will not work (I think there is something worng with template II)
so I take a step back and tried to came up with my own binary search for 2 search space and here is my template, there it is.
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (target < nums[mid]) {
right = mid - 1;
}
else if (target > nums[mid]) {
left = mid + 1;
}
else {
return mid;
}
}
if (nums[left] == target) {
return left;
}
return -1;
}
};
And it is accepted by leetcode binary search problem https://leetcode.com/problems/binary-search/
But wait this is looks exacly same as the template I with 2 differences
- while loop condition now (left < right) instead of (left <= right)
- there is post-processing condition
Exactly and that is what make it 2 search space
Why ?
will if you think about it every element you git with (nums[mid]) have right element and you can access it execpt for the last one and to avoid touching the last element we wrote (left < right) this conidtion won't let left to equal right so mid will never be the last index, now we have 2 search space but if you will use this template for accessing single element you have to write the post-processing condtion to check the only element you have never checked in the while loop and this element sitts at index (x) where x = left and x = right because when left get equals right the loop will breaks
now you can use this template to solve the problem that we came up with earlier
here is my solution
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (target < nums[mid] + nums[mid + 1]) {
right = mid - 1;
}
else if (target > nums[mid] + nums[mid + 1]) {
left = mid + 1;
}
else {
return mid;
}
}
if (left < nums.size() - 1 && nums[left] + nums[left + 1] == target) {
return left;
}
return -1;
}
};
int main(void) {
Solution solution;
vector<int> nums = { 1, 2, 3, 4 };
cout << solution.search(nums, 7) << endl;
cout << solution.search(nums, 9) << endl;
}