注意事项：
← 内容总览 02 / 24 下一节 → 强化讲义 · 原始转写 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照
## 注意事项：
快速排序不是万能的，有如下情况下不能使用：
题目明示或暗示不能改变顺序表元素的次序。
要采用稳定的排序算法。
如果题目需要得到降序，有两种方法：
方法1：修改快速排序代码（适合基础好的同学)。
方法2：快速排序代码不变，主过程段新增 for 循环将数组逆置。for (int i=0;i < n/2;
i++) swap(A[i], A[n-i-1]);
正常情况下快速排序代码可以直接默写，但如果数组的类型不是int 就需要修改。
<!-- page 12 -->
## 2.3 判断能否优化
写出暴力解后，下一步就是思考优化的可能性。从以下两个角度自问，往往能发现突破口：
1.“条件浪费”：题目中是否给了一些我没用上的重要条件？
例如：数组是“升序”的，但我却从头到尾线性扫描，浪费了有序性。
例如：元素值范围是“0到n-1”，但我却用了排序，浪费了数据范围的特性。
2.“目标超额”：我为了解决问题，是不是做了很多额外的不必要工作？
例如：题目只要求“找出最小值”，我却把整个数组都排序了。
例如：题目只要求“把小于k的放左边，大于等于k的放右边”，我却把左右两边的元素内部都排好序了。
最好的算法，就是把题目的所有条件都榨干，并且不做多余的操作。
## 思考：下面几种暴力解分别符合哪个标准
例题 2-1：对升序数组 A，求是否存在值为 x的元素，存在返回1，不存在返回-1。暴力解：枚举 A
例题 2-2：将两个升序数组 A 和 B 合并成一个新的升序数组 C。暴力解：快速排序
例题2-3：数组 A 中有 n 个非负元素，每个元素绝对值< n，其中只有一个数重复出现过，请输出这个数。暴力解：枚举
例题2-4：求含n个数（n为奇数）的数组A的中位数。暴力解：快速排序
例题 2-5：已知数组 A 含有n 个整数，现在要将小于 k的元素放在数组左侧，大于等于 k的元素放在右侧，如何实现这个功能。暴力解：快速排序
例题 2-6：已知数组 A 含有 n 个整数，现在要求另一个数组 res，res[i] 表示长度为 i+1 的连续子序列中元素和的最大值，求res数组。暴力解：枚举 人
<!-- page 13 -->
## 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=1 colspan=1>边界更新逻辑</td><td rowspan=1 colspan=1>R = mid - 1 或 L = mid+ 1 (直接排除 mid)</td><td rowspan=1 colspan=1>R = mid 或 L = mid + 1(可能不能排除 mid)</td></tr></table>
## 模板一：『等值判断』
这是最基础、最常用的模板，其核心是在循环内部通过 if（A[mid] == 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 ] == x )
return mid ; // 查找成功
else
if ( x & lt ; A [ mid ])
R = mid - 1 ; // x 在左半区间，L ~ mid-1
else L = mid + 1 ; // x 在右半区间, mid+1
}
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 )
return mid ; //查找成功
else
if ( x & lt ; A [ mid ])
R = mid - 1 ; // x 在左半区间 ~ mid-1
else L = mid + 1 ; // x 在右半区间， mid+1 ∼ R
}
return -1 ; //查找失败
}
//在升序数组A中判断是否存在
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 ;
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 )
{
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数组
}
void ans ( int A [], int n )
{
int res [ n ], B [ n ];
int B [ 0 ] = A [ 0 ];
for ( int i = 1 ; 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 = A [ 0 ];
for ( int j = 0 ; j & lt ; n ; j ++ )
{
B = max ( B , A [ j ]);
res [ j ] = B * A [ j ];
}
输出res数组
}
← 内容总览 02 / 24 下一节 →