LintCode 搜索插入位置题目分析代码

题目

给定一个排序数组和一个目标值,如果在数组中找到目标值则返回索引。如果没有,返回到它将会被按顺序插入的位置。 你可以假设在数组中无重复元素。

样例 [1,3,5,6],5 → 2 [1,3,5,6],2 → 1 [1,3,5,6], 7 → 4 [1,3,5,6],0 → 0

分析

显然这道题就是一道简单的查找题,采用二分查找的算法,最后在尝试给出返回值就可以了,这题较为简单

代码

public class Solution {
    /** 
     * param A : an integer sorted array
     * param target :  an integer to be inserted
     * return : an integer
     */
    public int searchInsert(int[] A, int target) {
        // write your code here
        if(A.length == 0)
            return 0;
        if(A == null)
            return -1;
        int lo = 0;
        int hi = A.length - 1;
        int mid;
        while(lo <= hi)
        {
            mid = (hi-lo)/2 + lo;
            if(target < A[mid])
                hi = mid-1;
            else if(target > A[mid])
                lo = mid+1;
            else
                return mid;
        }
        return lo;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏尾尾部落

[算法总结] 二分查找

二分查找法作为一种常见的查找方法,将原本是线性时间提升到了对数时间范围,大大缩短了搜索时间,但它有一个前提,就是必须在有序数据中进行查找。

2062
来自专栏开源优测

[快学Python3]二分查找[策略优化版本]

概述 在上文《二分查找》中,我们了解了二分查找基本实现原理和具体的实现算法。 但大家有没有发现,如果目标查找值,如果在查找序列中存在多个,则查找返回的索引值,会...

3195
来自专栏大神带我来搬砖

如何编写更优雅的代码——java中用break语句模拟goto来中止代码块的执行

根据https://docs.oracle.com/javase/specs/jls/se7/html/jls-14.html, java的break语句不仅可...

2639
来自专栏Petrichor的专栏

numpy: np.random模块 探究(源码)

2202
来自专栏数据结构与算法

1116 四色问题

1116 四色问题  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 黄金 Gold 题解 题目描述 Description 给定N(小于...

2845
来自专栏和蔼的张星的图像处理专栏

138. 子数组之和 map存储加规律

给定一个整数数组,找到和为零的子数组。你的代码应该返回满足要求的子数组的起始位置和结束位置。 假定一定存在这样的字数组。 样例 给出 [-3, 1, 2,...

1151
来自专栏CDA数据分析师

入门 | 数据科学初学者必知的NumPy基础知识

NumPy(Numerical Python)是 Python 中的一个线性代数库。对每一个数据科学或机器学习 Python 包而言,这都是一个非常重要的库,S...

1342
来自专栏机器学习从入门到成神

2013百度校招笔试真题以及解析(二)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

961
来自专栏数据结构与算法

P2590 [ZJOI2008]树的统计

题目描述 一棵树上有n个节点,编号分别为1到n,每个节点都有一个权值w。 我们将以下面的形式来要求你对这棵树完成一些操作: I. CHANGE u t : 把结...

2866
来自专栏Python小屋

详解Python列表推导式

列表推导式,也叫列表解析式,英文名称为list comprehension,可以使用非常简洁的方式来快速生成满足特定需求的列表,代码具有非常强的可读性。另外,P...

3294

扫码关注云+社区

领取腾讯云代金券