/* 求第一个大于等于value的位置x, 即[first0, x)都小于value, [x, last0)都大于等于value */
int lower_bound( vector<int> nums, int first, int last, int value )
{
while ( first < last ) /* 当fisrt==last时终止,此时[first, last)是空集 */
{
int mid = first + (last - first) / 2; /* 防止溢出 */
if ( nums[mid] < value )
first = mid + 1; /* [first0, first)范围内的元素都小于value */
else last = mid; /* [last, last0)范围内的元素都大于等于value */
}
return(first);
}
/* 求第一个大于value的位置x, 即[first0, x)都小于等于value, [x, last0)都大于value */
int upper_bound( vector<int> nums, int first, int last, int value )
{
while ( first < last )
{
int mid = first + (last - first) / 2;
if ( nums[mid] <= value )
first = mid + 1; /* [first0, first)范围内的元素都小于等于value */
else last = mid; /* [last, last0)范围内的元素都大于value */
}
return(first);
}
vector<int> searchRange( vector<int> & nums, int target )
{
int first = lower_bound( nums, 0, nums.size(), target );
int last = upper_bound( nums, 0, nums.size(), target );
if ( first == last )
return({ -1, -1 });
else
return({ first, last - 1 });
}
二分查找模板
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
- 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
推荐阅读更多精彩内容
- 本文介绍了我这半年以来,在刷题过程中使用“二分查找法”刷题的一个模板,包括这个模板的优点、使用技巧、注意事项、调试...