2.3 判断能否优化
← 内容总览 02 / 24 下一节 → 原始讲义 · 非增强校订版 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照
## 2.3 判断能否优化
写出暴力解后，下一步就是思考优化的可能性。从以下两个角度自问，往往能发现突破口：
1.“条件浪费”：题目中是否给了一些我没用上的重要条件？
。例如：数组是“升序”的，但我却从头到尾线性扫描，浪费了有序性。
。例如：元素值范围是“0到n-1”，但我却用了排序，浪费了数据范围的特性。
2.“目标超额”：我为了解决问题，是不是做了很多额外的不必要工作？
。例如：题目只要求“找出最小值”，我却把整个数组都排序了。
。例如：题目只要求“把小于k的放左边，大于等于k的放右边”，我却把左右两边的元素内部都排好序了。
最好的算法，就是把题目的所有条件都榨干，并且不做多余的操作。
思考：下面几种暴力解分别符合哪个标准
• 例题2-1：对升序数组A，求是否存在值为x的元素，存在返回1，不存在返回-1。
暴力解：枚举
• 例题 2-2：将两个升序数组A 和 B 合并成一个新的升序数组C。
暴力解：快速排序
• 例题2-3：数组A 中有n 个非负元素，每个元素绝对值<n，其中只有一个数重复出现过，请输出这个数。
暴力解：枚举
•例题2-4：求含n 个数（n为奇数）的数组A的中位数。
暴力解：快速排序
<!-- page 10 -->
• 例题2-5：已知数组A含有n 个整数，现在要将小于k的元素放在数组左侧，大于等于k的元素放在右侧，如何实现这个功能。 ka
暴力解：快速排序
• 例题 2-6：已知数组 A 含有 n 个整数，现在要求另一个数组 res，res[i] 表示长度为 i+1 的连续子序列中元素和的最大值，求 res 数组。
暴力解：枚举
## 2.4 优化解
针对前文分析，我们介绍几种核心的优化思想。
## 2.4.1 折半查找
核心要素：
• 使用条件：有序的顺序表（数组）。
• 核心思想：通过不断与区间中点比较，每次都将查找范围缩小一半。
• 复杂度： 时间 O(logn)，空间 O(1)。
当题目出现“有序数组”(且是顺序表，不是链表)时，你的脑海里应该立刻响起“折半查找”的警报，真题中频繁考察。
## 两种经典模板
<table><tr><td rowspan=1 colspan=1>对比项</td><td rowspan=1 colspan=1>模板一：『等值判断』模板（优先使用）</td><td rowspan=1 colspan=1>模板二：『区间收敛』模板</td></tr><tr><td rowspan=1 colspan=1>适用场景</td><td rowspan=1 colspan=1>查找一个确切的值，通常适合元素不重复。</td><td rowspan=1 colspan=1>查找满足条件的第一个或最后一个元素，元素可以重复。</td></tr><tr><td rowspan=1 colspan=1>查找成功</td><td rowspan=1 colspan=1>A[mid] == x 判断。</td><td rowspan=1 colspan=1>区间缩小为只有一个元素，需额外判断。</td></tr><tr><td rowspan=1 colspan=1>查找失败</td><td rowspan=1 colspan=1>区间中没有元素</td><td rowspan=1 colspan=1>区间缩小为只有一个元素，需额外判断。</td></tr><tr><td rowspan=1 colspan=1>循环条件</td><td rowspan=1 colspan=1>while （L <= R） (区间没有元素时退出循环)</td><td rowspan=1 colspan=1>while（L < R） (区间收敛为一个元素时退出循环)</td></tr><tr><td rowspan=2 colspan=1>边界更新逻辑</td><td rowspan=1 colspan=1>R = mid - 1 或 L = mid + 1 (直接排</td><td rowspan=2 colspan=1>R = mid 或 L = mid + 1 (可能不能排除 mid)</td></tr><tr><td rowspan=1 colspan=1>除mid)</td></tr></table>
## 模板一：『等值判断』
这是最基础、最常用的模板，其核心是在循环内部通过 if （A[mid] == x） 直接判断是否找到了目标值。
<!-- verified-by-hand -->
> [!success] 已结合原文第 10 页及 Markdown 上下文人工校对
> 结合同讲义后文模板逐行校正：补回 while 循环体花括号，拆开被串行的 mid 赋值和 if，将 return -1 放回循环之后
// 折半查找
int B_Search ( int A [], int L , int R , int x )
{
int mid ;
while ( L & lt ; = R )
{
mid = ( R + L ) / 2 ; // 求中点
if ( A [ mid ] == x )
return mid ; // 查找成功
else if ( x & lt ; A [ mid ])
R = mid - 1 ; // x 在左半区间
else
L = mid + 1 ; // x 在右半区间
}
return -1 ; // 查找失败
}
// 折半查找第一个等于 x 元素的下标
int B_Search ( int A [], int L , int R , int x )
{
int mid ;
while ( L & lt ; R ) //缩小区间直到区间只有一个元素
{
mid = ( R + L ) / 2 ;
if ( A [ mid ] & gt ; = x ) R = mid ; // 第一个等于 x 元素的下标在 L ～ mid
else L = mid + 1 ; // 第一个等于 x 元素的下标在 mid+1 ~ R
}
return L ; //可能查找成功也可能失败，需额外判断
}
//折半查找模板一
int B_Search ( int A [], int L , int R , int x )
{
int mid ;
while ( L & lt ; = R ) //只要区间不为空就继续
{
mid = ( R + L ) / 2 ; //求中点
}
}
if ( A [ mid ] == x )
else return mid ; //查找成功
if ( x & lt ; A [ mid ])
R = mid - 1 ; // x 在左半区间，L ~ mid-1
else L = mid + 1 ; // x 在右半区间，mid+1 ～ R
}
return -1 ; //查找失败
// 在升序数组 A 中判断是否存在 x
int ans ( int A [], int n , int x )
{
//直接调用折半查找函数
if ( B_Search ( A , 0 , n - 1 , x ) == -1 )
return -1 ;
else return 1 ;
//折半模板二
int B_Search ( int A [], int L , int R , int x )
{
int mid ;
while ( L & lt ; R )
{
mid = ( L + R ) / 2 ;
if ( A [ mid ] & gt ; = x ) R = mid ; Ww w
else L = mid + 1 ;
}
return L ;
// 在升序数组 A 中查找第一个等于 x 的元素的位置
int ans ( int A [], int n , int x )
{
int pos = B_Search ( A , 0 , n - 1 , x );
if ( A [ pos ] == x ) return pos ; //查找成功
else return -1 ; //查找失败
}
}
void Hash ( int A [], int n )
{
//辅助数组充当散列表，大小为 n，下标 0 ~ n-1
int count [ n ] = { 0 }; //需要初始化
for ( int i = 0 ; i & lt ; n ; i ++ )
{
// A[i] 的值在 0 到 n-1 之间，可以直接用作 count 数组的下标
if ( count [ A [ i ]] & gt ; 0 )
输出 A [ i ]; // 说明 A[i] 之前出现过
count [ A [ i ]] ++ ; //标记 A[i] 出现
}
} 专研
int ans ( int A [], int n )
{
int count [ n + 2 ] = { 0 }; //0~n+1
for ( int i = 0 ; i & lt ; n ; i ++ ) //扫描数组A
if ( A [ i ] & gt ; 0 & amp ; & amp ; A [ i ] & lt ; = n + 1 ) // 当0<A[i]<=n+1时才修改
count [ A [ i ]] ++ ;
for ( int j = 1 ; j & lt ; = n + 1 ; j ++ ) //扫描count数组
if ( count [ j ] == 0 ) // j未出现过，是最小未出现正整数
return j ; //输出j
}
void ans ( int A [], int n )
{
// 创建将res数组初值设为最小负数
int res [ n ] = { 0 };
for ( int i = 0 ; i & lt ; n ; i ++ )
res [ i ] = INT_MIN ;
//枚举每种A[i~j]的连续子序列
for ( int i = 0 ; i & lt ; n ; i ++ )
for ( int j = i ; j & lt ; n ; j ++ )
{
int temp = 0 ;
for ( int k = i ; k & lt ; = j ; k ++ )
temp += A [ k ];
if ( temp & gt ; res [ j - i ])
res [ j - i ] = temp ;
}
输出res数组
}
void ans ( int A [], int n )
{
//创建并初始化前缀和数组
int res [ n ];
for ( int i = 0 ; i & lt ; n ; i ++ )
res [ i ] = INT_MIN ;
//创建并初始化前缀和数组
int sum [ n + 1 ] = { 0 };
for ( int i = 1 ; i & lt ; = n ; i ++ )
sum [ i ] = sum [ i -1 ] + A [ i -1 ];
//枚举每种A[i~j]的连续子序列
for ( int i = 0 ; i & lt ; n ; i ++ )
for ( int j = i ; j & lt ; n ; j ++ )
{
int temp = sum [ j + 1 ] - sum [ i ];
if ( temp & gt ; res [ j - i ])
res [ j - i ] = temp ;
}
输出res数组
}
void ans ( int A [], int n )
{
int res [ n ];
for ( int j = 0 ; j & lt ; n ; j ++ )
{
res [ j ] = INT_MIN ;
for ( int i = 0 ; i & lt ; = j ; i ++ )
if ( A [ i ] * A [ j ] & gt ; res [ j ]) res [ j ] = A [ i ] * A [ j ];
}
} 输出res数组 m
void ans ( int A [], int n )
{
int res [ n ], B [ n ];
int B [ O ] = INT_MIN ;
for ( int i = 0 ; i & lt ; n ; i ++ )
B [ i ] = max ( B [ i -1 ], A [ i ]);
for ( int j = 0 ; j & lt ; n ; j ++ )
res [ j ] = B [ j ] * A [ j ];
输出res数组
}
void ans ( int A [], int n )
{
int res [ n ];
int B = INT_MIN ;
for ( int j = 0 ; j & lt ; n ; j ++ )
{
B = max ( B , A [ j ]);
res [ j ] = B * A [ j ];
}
输出res数组
}
← 内容总览 02 / 24 下一节 →