算法-二分运算

二分分为整数二分和浮点二分，在整数二分中需要特别注意边界的细节

整数二分-求边界

pair<int, int> binary_search(const vector<int>& num, int target)
{
if (num.empty())
return { -1,-1 };
pair<int, int>ans = { -1,-1 };
int left = 0;
int right = num.size() - 1;
while (left < right)
{
int mid = (left + right) >> 1;
if (num[mid] >= target)
right = mid;
else
left = mid + 1;
}
if (num[left] != target)
return { -1,-1 };
ans.first = left;
left = 0;
right = num.size() - 1;
while (left < right)
{
int mid = (left + right + 1) >> 1;
if (num[mid] <= target)
left = mid;
else
right = mid - 1;
}
ans.second = left;
return ans;
}

需要特别注意，①边界条件是left < right，如果取等会有特别条件报错

②在数列单调递增的时候，左边界应是num[mid] >= target，但是如果是递减就要变成≤

③mid计算的时候是否加一取决于right是等于mid还是不动，如果不动则需要加一（或者理解为left等于mid的时候需要加一）

如果元素至多一个，便会简单很多

int binary_search(const vector<int>& num, int target)
{
int left = 0;
int right = num.size() - 1;
while (left <= right)
{
int mid = (left + right) >> 1;
if (num[mid] > target)
right = mid - 1;
else if (num[mid] == target)
return mid;
else
left = mid + 1;
}
return -1;
}

此时条件直接left <= right即可

浮点二分

double binary_search(double left, double right)
{
double gap = 1e-6;
while (right - left > gap)
{
double mid = (left + right) / 2;
if (check(left))
left = mid;
else
right = mid;
}
return left;
}

具体例子：求平方根

double binary_search(double num)
{
if (num < 0)
return -1;
double gap = 1e-6;
double left = 0;
double right = max(1.0, num);
while (right - left > gap)
{
double mid = (left + right) / 2;
if (mid * mid > num)
right = mid;
else
left = mid;
}
return left;
}

值得注意，gap的取值应该小于题目要求答案精度的1%