二分法及其变体问题

1.寻找一个元素在数组中的位置

//二分查找
int midfind1(int lo,int hi,int tar) {
	int mid;
	while (lo <= hi)
	{
		mid = lo + (hi - lo) / 2;
		if (a[mid] > tar) hi = mid - 1;
		else if (a[mid] < tar) lo = mid + 1;
		else return mid;
	}
	return -1;
}

2.查找第一个等于给定值的元素

//查找第一个等于给定值的元素
int firstEqPos(int lo, int hi, int tar) 
{
	int mid ;
	while (lo <= hi)
	{
		mid = lo + ((hi - lo)>>1);
		if (a[mid] > tar) hi = mid - 1;
		else if (a[mid] < tar) lo = mid + 1;
		else {
			if (mid == 0 || a[mid - 1] != tar) return mid;
			else hi = mid - 1;
		}
	}
	return -1;
}

3.查找最后一个等于给定值的元素

int lastEqPos(int lo, int hi, int tar)
{
	int mid;
	int n = hi;
	while (lo <= hi)
	{
		mid = lo + ((hi - lo) >> 1);
		if (a[mid] > tar) hi = mid - 1;
		else if (a[mid] < tar) lo = mid + 1;
		else {
			if (mid == n || a[mid+1] != tar) return mid;
			else lo = mid + 1;
		}
	}
	return -1;
}

4.查找第一个大于等于给定值的元素

int firstBigPos(int lo, int hi, int tar)
{
	int mid;
	while (lo <= hi)
	{
		mid = lo + ((hi - lo) >> 1);
		if (a[mid] < tar) lo = mid +1;
		else {
			if (mid == 0 || a[mid - 1] < tar) return mid;
			else hi = mid - 1;
		}
	}
	return -1;
}

 5.查找最后小于等于给定值的原素

int lastLitPos(int lo, int hi, int tar)
{
	int mid;
	int n = hi;
	while (lo <= hi)
	{
		mid = lo + ((hi - lo) >> 1);
		if (a[mid] > tar) hi = mid - 1;
		else {
			if (mid == n || a[mid + 1] > tar) return mid;
			else lo = mid + 1;
		}
	}
	return -1;
}