二分法及其变形
程序员文章站
2024-03-16 08:52:34
...
二分法及其变形(c++)
1. 基本形式,查找数组等于目标值的下标(数组中不含重复性)
int barrysearch(vector &a,int target)
{
int left = 0, right = a.size() - 1; //left,right的初始值
while (left <= right) //循环退出条件
{
int mid = left + (right - left) / 2;
if (a[mid] == target)
return mid;
else if (a[mid] > target)
right = mid - 1;
else left = mid + 1;
}
return -1;
}
- 排序数组中存在重复值,查找第一个等于目标值的下标
int barrysearch1(vector<int> &a, int target)
{
int left = 0, right = a.size() - 1; //left,right的初始值
while (left <= right) //循环退出条件
{
int mid = left + (right - left) / 2;
if (a[mid] > target)
right = mid - 1;
else if (a[mid] < target)
left = mid + 1;
else
{
if (mid == 0 || a[mid - 1] != target) //判断mid是前一个值是否也等于目标值。若不等于则返回mid
return mid;
else right = mid - 1; //若mid 前一个值也等于目标值,说明mid不是第一个等于目标值的下标,继续缩小查找范围
}
}
return -1;
}
- 排序数组中存在重复值,查找最后一个等于目标值的下标(思路与2类似)
int barrysearch2(vector<int> &a, int target)
{
int left = 0, right = a.size() - 1; //left,right的初始值
while (left <= right) //循环退出条件
{
int mid = left + (right - left) / 2;
if (a[mid] > target)
right = mid - 1;
else if (a[mid] < target)
left = mid + 1;
else
{
if (mid ==a.size()-1|| a[mid+1] != target)
return mid;
else left = mid+1;
}
}
return -1;
}
- 查找排序数组中,第一个大于等于目标值的下标(数组中可能不存在目标值)
int barrysearch3(vector<int> &a, int target)
{
int left = 0, right = a.size() - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (a[mid] < target) //若a[mid]小于目标值,直接缩小范围
left = mid + 1;
else if (a[mid] >= target)
{
if (mid == 0 || a[mid - 1] < target) //在a[mid]大于等于目标值的情况下,需要判断mid是否是第一个大于等于目标值的下标,若是就直接返回
return mid;
else right = mid - 1;
}
}
return -1;
}
- 查找排序数组中,最后一个小于等于目标值的下标(数组中可能不存在目标值)
int barrysearch4(vector<int> &a, int target)
{
int left = 0, right = a.size() - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (a[mid]>target)
right= mid-1;
else if (a[mid]<=target)
{
if (mid ==a.size()-1|| a[mid+1] > target) //思路参考3
return mid;
else left=mid+1;
}
}
return -1;
}