文档章节

二分搜索专题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

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周一乱弹 —— 鱼生不值得

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @瘟神灬念:分享新裤子的单曲《没有理想的人不伤心 (Remix版)》: 《没有理想的人不伤心 (Remix版)》- 新裤子 手机党少年们想听歌,请使劲儿戳...

小小编辑
18分钟前
4
3
arts-week10

Algorithm 905. Sort Array By Parity - LeetCode Review Who’s Afraid of the Big Bad Preloader? 一文读懂前端缓存 一个网络请求3个步骤:请求,处理,响应,而前端缓存主要在请求处响应这两步...

yysue
今天
4
0
00.编译OpenJDK-8u40的整个过程

前言 历经2天的折腾总算把OpenJDK给编译成功了,要说为啥搞这个,还得从面试说起,最近出去面试经常被问到JVM的相关东西,总感觉自己以前学的太浅薄,所以回来就打算深入学习,目标把《深入理...

凌晨一点
今天
5
1
python: 一些关于元组的碎碎念

初始化元组的时候,尤其是元组里面只有一个元素的时候,会出现一些很蛋疼的情况: def checkContentAndType(obj): print(obj) print(type(obj))if __name__=="__main__": tu...

Oh_really
昨天
6
2
jvm crash分析工具

介绍一款非常好用的jvm crash分析工具,当jvm挂掉时,会产生hs_err_pid.log。里面记录了jvm当时的运行状态以及错误信息,但是内容量比较庞大,不好分析。所以我们要借助工具来帮我们。 Cras...

xpbob
昨天
180
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部