文档章节

二分搜索专题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
2018/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
麻省:第11课

1.testing 单元测试:分别验证程序中每块独立的部分 集成测试:把整个程序组合起来验证 测试集:必须小到一个合理的时间去完成它 2.debugging 搜索的过程 发现问题: 1.阅读文本,并思考怎么...

finndai
2016/10/11
5
0

没有更多内容

加载失败,请刷新页面

加载更多

centos7重置密码、单用户模式、救援模式、ls命令、chmod命令

在工作当中如果我们错误的配置了文件使服务器不能正常启动或者忘记密码不能登录系统,如何解决这些问题呢?重装系统是可以实现的,但是往往不能轻易重装系统的,下面用忘记密码作为例子讲解如...

李超小牛子
今天
3
0
Python如何开发桌面应用程序?Python基础教程,第十三讲,图形界面

当使用桌面应用程序的时候,有没有那么一瞬间,想学习一下桌面应用程序开发?行业内专业的桌面应用程序开发一般是C++,C#来做,Java开发的也有,但是比较少。本节课会介绍Python的GUI(图形用...

程序员补给栈
今天
5
0
kafka在的使用

一、基本概念 介绍 Kafka是一个分布式的、可分区的、可复制的消息系统。它提供了普通消息系统的功能,但具有自己独特的设计。 这个独特的设计是什么样的呢? 首先让我们看几个基本的消息系统...

狼王黄师傅
今天
3
0
Android JNI总结

0x01 JNI介绍 JNI是Java Native Interface的缩写,JNI不是Android专有的东西,它是从Java继承而来,但是在Android中,JNI的作用和重要性大大增强。 JNI在Android中起着连接Java和C/C++层的作...

天王盖地虎626
昨天
3
0
大数据教程(11.8)Hive1.2.2简介&初体验

上一篇文章分析了Hive1.2.2的安装,本节博主将分享Hive的体验&Hive服务端和客户端的使用方法。 一、Hive与hadoop直接的关系 Hive利用HDFS存储数据,利用MapReduce查询数据。 二、Hive与传统数...

em_aaron
昨天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部