欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二分法及其变形

程序员文章站 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;
}

  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;
}
  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;
}
  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;
}
  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;
}