by 光城
基于二分搜索法的floor与ceil
1.基本的二分搜索
在闭区间[left,right]范围内查找target。
class Solution {
public:
int search1(vector<int>& nums, int target) {
if (nums.size() == 0) return -1;
int left = 0, right = nums.size()-1;
// left与right均不会越界，可以取等
while (left <= right) {
int mid =left+ (right-left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1; // mid处理过了，需要mid+1
} else if (nums[mid] > target) {
right = mid-1; // mid处理过了,需要mid-1
}
}
return -1;
}
};
如果上述right改为nums.size()，判断与right均会发生变化：
此时处理的范围为[left,right)
class Solution {
public:
int search2(vector<int>& nums, int target) {
if (nums.size() == 0) return -1;
int left = 0, right = nums.size();
// right会越界
while (left < right) {
int mid =left+ (right-left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1; // mid处理过了，需要mid+1 left不会越界
} else if (nums[mid] > target) {
right = mid; // 处理范围为[left,right)，right为开区间，不可取得right，一定要维护[left,right)这个条件不变
}
}
return -1;
}
};
上述都比较简单，现在我们考虑有如下例子：
vector<int> nums={1,2,2,2,2,3,5};
int target=2;
此时使用上述二分查找算法，搜索出来的index为3。那如果我想要获取最左侧等于target的index或最右侧等于target的index呢？此时上述算法失效！
2.最左侧index
所谓最左侧index为第一个等于target对应的index
class Solution {
public:
int search3(vector<int>& nums, int target) {
if (nums.size() == 0) return -1;
int left = 0, right = nums.size()-1;
while (left <= right) {
int mid =left+ (right-left) / 2;
if (nums[mid] == target) {
right=mid-1;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid-1;
}
}
if(left==nums.size()) return -1; // 如果最后left==nums.size()，表示nums中的所有元素都小于target,查找失败！
return nums[left] == target ? left : -1;
}
};
3.最右侧index
所谓最右侧index为最后一个等于target对应的index
class Solution {
public:
int search4(vector<int>& nums, int target) {
if (nums.size() == 0) return -1;
int left = 0, right = nums.size()-1;
while (left <= right) {
int mid =left+ (right-left) / 2;
if (nums[mid] == target) {
left = mid + 1; // 注意
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid-1;
}
}
if(right<0) return -1; // 或者写if(left==0) return -1; 如果right<0，那么此时nums中所有元素均大于target
return nums[right] == target ? right : -1;
}
};
测试上述算法：
int main() {
vector<int> nums={1,2,2,2,2,3,5};
int target=2;
cout<<Solution().search1(nums,target)<<endl; // 3
cout<<Solution().search2(nums,target)<<endl; // 3
// 寻找第一个等于target的index,最左侧index
cout<<Solution().search3(nums,target)<<endl; // 1
cout<<Solution().search4(nums,target)<<endl; // 4
return 0;
}
测试成功。
4.floor
对于上述最左侧index，我们可以将这个算法的返回值进行修改，这样就得到了我们想要的floor函数，floor函数定义是：当存在大量重复元素时，floor找的是第一个，当不存在指定的元素时，floor找的是比其小最大的一个。
注意边界，当所有元素小于target时，返回的index为最后一个index，当所有元素大于target时，返回-1.
class Solution {
public:
int floor1(vector<int>& nums, int target) {
if (nums.size() == 0) return -1;
int left = 0, right = nums.size()-1;
while (left <= right) {
int mid =left+ (right-left) / 2;
if (nums[mid] == target) {
right=mid-1;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid-1;
}
}
// 所有元素均大于target
if (right < 0) return -1;
// 所有元素均小于target
if (left == nums.size()) return left - 1;
return nums[left] == target ? left : left-1;
}
};
将该算法使用另外一种写法：
使用(left,right]定义
int floor2(vector<int>& nums, int target) {{
// 寻找比target小的最大索引
int left = -1, right = nums.size()-1;
// (left,right]
while( left < right ){
// 使用向上取整避免死循环
int mid = left + (right-left+1)/2;
if( nums[mid] >= target )
right = mid - 1;
else
left = mid;
}
// 如果该索引+1就是target本身, 该索引+1即为返回值
if( left + 1 < nums.size() && nums[left+1] == target )
return left + 1;
// 否则, 该索引即为返回值
return left;
}
5.ceil
对于上述最右侧index，我们可以将这个算法的返回值进行修改，这样就得到了我们想要的ceil函数，ceil函数定义是：当存在大量重复的元素时，ceil找的是第一个。当不存在指定的元素时，ceil是比其大最小的一个。
注意边界，当所有元素小于target时，返回的index为最后一个index，当所有元素大于target时，返回0.
class Solution {
public:
int ceil1(vector<int>& nums, int target) {
if (nums.size() == 0) return -1;
int left = 0, right = nums.size()-1;
while (left <= right) {
int mid =left+ (right-left) / 2;
if (nums[mid] == target) {
left = mid + 1; // 注意
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid-1;
}
}
// 所有元素均大于target
if (right < 0) return 0;
// 所有元素均小于target
if (left == nums.size()) return left - 1;
return nums[right] == target ? right : right+1;
}
};
将该算法使用另外一种写法：
使用(left,right]定义
int ceil2(vector<int>& nums, int target) {
// 寻找比target大的最小索引值
int left = 0, right = nums.size()-1;
while( left < right ){
// 使用普通的向下取整即可避免死循环
int mid = left + (right-left)/2;
if( nums[mid] <= target )
left = mid + 1;
else // arr[mid] > target
right = mid;
}
// 如果该索引-1就是target本身, 该索引+1即为返回值
if( right - 1 >= 0 && nums[right-1] == target )
return right-1;
// 否则, 该索引即为返回值
return right;
}
6.全部算法测试
int main() {
vector<int> nums = {1, 2, 2, 2, 2, 3, 5};
int target = 2;
cout << Solution().search1(nums, target) << endl; // 3
cout << Solution().search2(nums, target) << endl; // 3
// 寻找第一个等于target的index,最左侧index
cout << Solution().search3(nums, target) << endl; // 1
cout << Solution().search4(nums, target) << endl; // 4
cout << Solution().ceil1(nums, 0) << endl; // 0
cout << Solution().ceil2(nums, 0) << endl; // 0
cout << Solution().ceil1(nums, 4) << endl; // 5
cout << Solution().ceil2(nums, 4) << endl; // 5
cout << Solution().ceil1(nums, 6) << endl; // 6
cout << Solution().ceil2(nums, 6) << endl; // 6
cout << Solution().floor1(nums, 0) << endl; // -1
cout << Solution().floor2(nums, 0) << endl; // -1
cout << Solution().floor1(nums, 4) << endl; // 5
cout << Solution().floor2(nums, 4) << endl; // 5
cout << Solution().floor1(nums, 6) << endl; // 6
cout << Solution().floor2(nums, 6) << endl; // 6
return 0;
}
