《算法设计》求单峰数组
2023-09-11 14:19:04 时间
这是算法设计书地171页上的题:假设有n个项的数组A,数组的每个元素都不相同,该数组序列是单峰的:对于某个在0与n-1之间的下标p,
数组项的值增加直到A中的位置p,然后剩下的元素减少直到位置n,
要求:尽量读很少的元素,就是找到这个顶峰元素p在哪一个位置,下面是具体的递归实现
ublic class FindMaxIndex {
public static int findMaxIndex(int arr[], int begin, int end) {
int center = (begin + end) / 2;
//如果中间元素处于上坡的位置
if (arr[center] > arr[center - 1] && arr[center] < arr[center + 1]) {
begin = center + 1;
return findMaxIndex(arr, begin, end);
}//如果处于下坡的位置
else if (arr[center] < arr[center - 1] && arr[center] > arr[center + 1]) {
end = center -1;
return findMaxIndex(arr, begin, end);
} else {//此种情况是当arr[center-1]<arr[center]<arr[center+1]因为此数组是单峰数组,
return center;
}
}
public static void main(String[] args) {
int arr[] = {1, 2, 3, 5,6, 7, 8,9,10,4, 3, 2, 1};
System.out.println(FindMaxIndex.findMaxIndex(arr, 0, arr.length));
}
}
相关文章
- 朴素贝叶斯分类算法-----java
- 【算法】【字符串模块】重新排列字符串数组使得字符串数组整体顺序最小或最大
- 【算法】【递归与动态规划模块】两个字符串的最长公共子数组
- 【算法】【栈和队列模块】将数组转为最大值树MaxTree
- 基于级联FFT的广义互相关算法在声源定位中的应用
- 基于64QAM的LDPC编译码算法
- R语言数据挖掘2.2.5 基于最大频繁项集的GenMax算法
- JS 数组中找到与目标值最接近的数字,记一次工作中关于二分查找的算法优化
- 【算法】提高效率/刷题工具
- dijkstra算法 模板
- 【转载】 详解BN(Batch Normalization)算法
- 猿创征文|【算法入门必刷】数据结构-栈(二)
- 整型数组处理算法(十一)请实现一个函数:线段重叠。[风林火山]
- 算法训练 FBI树(易懂的数组方法)
- 华为OD机试 - 最左侧冗余覆盖子串(JavaScript) | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 - 单词倒序(Python) | 机试题+算法思路+考点+代码解析 【2023】
- 秒懂算法 | 搜索基础
- 算法8:巧妙的邻接表(数组实现)
- leetcode算法108.将有序数组转换为二叉搜索树