文档章节

二分搜索专题1-在非递减数组中寻找满足A[i]=i的i

BlackJoker
 BlackJoker
发布于 2015/10/13 13:24
字数 254
阅读 4
收藏 0
在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]的区间

欢迎网友的指导。

© 著作权归作者所有

共有 人打赏支持
BlackJoker
粉丝 1
博文 17
码字总数 9270
作品 0
深圳
高级程序员
私信 提问
leetcode算法题解(Java版)-13-经典反转链表

一、简单二分搜索 题目描述 Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in or......

kissjz
05/19
0
0
在有序矩阵中查找一个值 Search a 2D Matrix

问题: Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties: Integers in each row are sorted from left to right. T......

叶枫啦啦
2017/09/16
0
0
面试四: 查找排序

面试官还问了我另外一个问题,就是给我一个严格递增或是严格递减的数组,让我将里面的某个数据取出来,这不就是折半查找吗? 下面我就整理一下二分查找: 算法复杂度:折半搜索每次把搜索区域...

botaorain
2014/09/25
0
0
从零基础学三分查找

转载请注明:http://www.cnblogs.com/ECJTUACM-873284962/ 今晚是我们学长第二次讲课,讲了一个三分!认真听了一下,感觉不是很难,可能会比二分还简单些!我就把上课讲的内容归纳为一篇文章...

angel_kitty
2017/03/11
0
0
二分法模板

二分思想:我们对于一个已经排好序的数组,查找某个值的位置(一般为从小到大排序,如为从大到小排序代码会有变动,以下代码均为从小到大排序的代码) 首先最简单的思想肯定是一个for循环扫一...

ZscDst
2017/11/01
0
0

没有更多内容

加载失败,请刷新页面

加载更多

数据集可视化---张量场的可视表示

中国龙-扬科
3分钟前
0
0
JavaScript创建对象方法实例小结

本文实例讲述了JavaScript创建对象方法。分享给大家供大家参考,具体如下: 最简单的方式就是创建一个Object对象,并为其添加属性和方法。 //示例代码var person=new Object()person.name=...

peakedness丶
5分钟前
0
0
GO 读写锁实现原理剖析

前言 TODO:简单说明读写锁用法及规则。 读写锁数据结构 类型定义 TODO: 源码中数据结构 TODO:讲解每个成员作用 写锁阻止写锁 TODO:描述两个尝试写是如何避免的 写锁阻止读锁 TODO:描述获...

恋恋美食
9分钟前
0
0
Java核心(二)深入理解线程池ThreadPool

本文你将获得以下信息: 线程池源码解读 线程池执行流程分析 带返回值的线程池实现 延迟线程池实现 为了方便读者理解,本文会由浅入深,先从线程池的使用开始再延伸到源码解读和源码分析等高...

王磊的博客
10分钟前
1
0
web项目中的乱码问题原理分析

Java web开发过程经常遇到乱码,本篇我们探讨一下乱码产生的原因与解决思路。 一次完整的Web请求会有4次编解码转换,如下所示。 第一次:客户端(通常为浏览器)将字符转换成TCP字节流发向服...

fame_yao
14分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部