在javaeye上看到了一个二分搜索相关的提问http://www.iteye.com/topic/1118606,我设计了一个简洁高效的算法,这里贴出来:
题目:对于一个非递减数组A,存在A[i]=i,求o(lgn)的算法找出i,
分析:
1,对于任意的j和i,如果j>i则A[j]>=A[i];
2,假设所求的解是I,即A[I]=I,则对任意的j,如果A[j]>j,可以得到I<j,如果A[j]<j,则j<I,如果A[j]=j,则j=I(不考虑I的多解情况).
利用2可以得到下面的算法:
public static int search(int[] A) {
int len = A.length;
int start = 0;
int end = len;
while (start <= end) {
int j = (start + end) / 2;
if (A[j] == j) {
return j;
}
if (A[j] > j) {
end = j - 1;
} else if (A[j] < j) {
start = j + 1;
}
}
return -1;
}
解析:
当A[j]>j时,抛弃[j,end]的区间,当A[j]<j时,抛弃[start,j]的区间
欢迎网友的指导。
分享到:
相关推荐
如果数组中不存在目标值 target,返回 [-1, -1]。 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。 示例 1: 输入:nums = [5,7,7,8,8,10], target = 8 输出:[3,4] 示例 2: 输入:nums = [5,7,7,8,8...
给定一个长度为 n 的整数数组,你的任务是判断在最多改变 1 个元 素的情况下,该数组能否变成一个非递减数列。非递减数列定义如下:对 于数组中所有的 i (1 <= i ),满足 array[i] <= array[i + 1]
输入两个数,查找位于位于这两数区间的序列
两数之和 II - 输入有序数组给定一个已按照 非递减顺序排列 的整数数组 numbers ,请你从数组中找出两个数满足相加之和等于目标数 target 。示例
36-数码管递加递减带消隐(51单片机C语言实例Proteus仿真和代码)36-数码管递加递减带消隐(51单片机C语言实例Proteus仿真和代码)36-数码管递加递减带消隐(51单片机C语言实例Proteus仿真和代码)36-数码管递加递减带消隐...
c语言 c语言编程题之数组操作非递减序列
# 给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。 # 输入示例 # 输入:nums = [-4,-1,0,3,10] # 输出:[0,1,9,16,100] # 解释:平方后,数组变为 [16,...
示例 2:输出:[1,3]示例 3:输出:[1,2]提示:numbers 按 非递减顺序 排列仅存在一个有效答案Related Topics数组双指针二分查找。
采用二分查找:如果数组中的数字小于下标,由于下标是-1的递减数列,但是数组中的元素差值大于等于-1,因此左边的不可能等于下标。如果数组中的数字大于下标,同理,之后的数字肯定都大于下标,往左边查找。 算法...
两个升序的数组A、B,将AB合并到C,保持升序,去除重生的元素
输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。 解题思路参考博客
matlab中如何创建数组: 使用方括号创建数组; 创建二维数组; 逗号+分号的形式创建数组; 使用冒号创建数组; 间距固定的递增或递减数组; 使用函数linspace创建数组; 使用函数logspace创建数组; 采用...
单片机C语言实例--36-数码管递加递减带消隐.zip
内容及步骤: 1、 设有一个线性表(e0,e1,e2,e3,…,en-2,en-1)存放在一个一维数组A[arraySize]中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置,即将数组的前n个原地址内容置换为(en-1,en-2,…,e3,...
An,求这个序列中最长的递减子序列的长度M, 以及该序列可以划分成这种子序列的个数N 如序列: 300 250 252 275 200 138 245 折分成的子序列分别为 300 275 200 138 252 245 250 其中最长序列为: 300 275 200 138 ...
内层循环控制每一轮比较的次数 最多的一次 长度-1 -i 并且是依次递减的 **( n -1 -i )** 2.选择排序: 选择排序和冒泡排序 比较的次数是一样 n-1 唯独区别在与:冒泡是立即调换位置 而选择是当一轮比较...
例如,在图1-1中,根结点A在第1层,结点B,C在第2层,结点D,E,F在第3层。该树的深度为3。 子树 在树中,以某结点的一个子结点为根构成的树称为该结点的一棵子树。 2. 二叉树基本性质 二叉树具有以下几个性质: ...
51单片机教程实例36-数码管递加递减带消隐
initVal:step:endVal - 每次迭代时按值 step 对 index 进行递增,或在 step 是负数时对 index 进行递减。 valArray - 每次迭代时从数组 valArray 的后续列创建列向量 index。例如,在第一次迭代时,index = ...
输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 又例如{1,0,1,1,1}和{1,1,1,0,1}都可以看成是递增排序数组{0,1,1,1,1}的...