搜索插入位置

题意

给定一个排序数组和一个目标值,如果在数组中找到目标值则返回索引。如果没有,返回到它将会被按顺序插入的位置。

你可以假设在数组中无重复元素。

样例

[1,3,5,6],5 → 2

[1,3,5,6],2 → 1

[1,3,5,6],7 → 4

[1,3,5,6],0 → 0

思路

跟普通的二分查找类似,循环的条件是 min <= max,如果 targetmid 指向的值相等,则返回 mid,否则根据情况 min = mid + 1 或者max = mid - 1。 这样如果找不到该数,max 是比该数小的那个数的下标,而 min 是比该数大的那个数的下标。这题中,我们返回 min 就行了,如果返回 max,要注意 -1 的情况。

代码实现

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) {
        int min = 0;
        int max = A.length - 1;
        
        if (A == null || A.length == 0) {
            return 0;
        }
        
        while (min <= max) {
            int mid = min +  (max - min) / 2;
            if (A[mid] == target) {
                return mid;
            }
            else if (A[mid] > target) {
                max = mid - 1;
            } else {
                min = mid + 1;
            }
            
        }
        return min;
    }
}

原题地址

LintCode:搜索插入位置

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏人工智能LeadAI

Python中对字节流/二进制流的操作:struct模块简易使用教程

前言 前段时间使用Python解析IDX文件格式的MNIST数据集,需要对二进制文件进行读取操作,其中我使用的是struct模块。查了网上挺多教程都写的挺好的,...

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

P3373 【模板】线段树 2 区间求和 区间乘 区间加

题目描述 如题,已知一个数列,你需要进行下面两种操作: 1.将某区间每一个数加上x 2.将某区间每一个数乘上x 3.求出某区间每一个数的和 输入输出格式 输...

412110
来自专栏wym

18年暑假多校赛第一场 1004

题目地址http://acm.hdu.edu.cn/showproblem.php?pid=6301

8820
来自专栏书山有路勤为径

逆序数

LeetCode 315. Count of Smaller Numbers After Self

7810
来自专栏debugeeker的专栏

《coredump问题原理探究》Linux x86版5.8节C风格数据结构内存布局之结构体数组结构体coredump

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

9310
来自专栏老秦求学

快速排序

快速排序: 设要排序的数组是A[0]……A[N-1], 思想:分治法(递归实现)关键是求出基准记录所在的位置(由于两个数之间进行交换,导致原来基准的位置发生改变...

29460
来自专栏codingforever

经典算法巡礼(四) -- 排序之希尔排序

希尔排序与之前的排序算法不同,她是以她的发明者Donald Shell来命名的。她是插入排序的一种改进版本。

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

06:整数奇偶排序

06:整数奇偶排序 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 给定10个整数的序列,要求对其重新排序。排序要求: 1...

41460
来自专栏vue学习

JS数据结构与算法-队列

11410
来自专栏Python小屋

Python中lambda表达式的常见用法

非常抱歉,昨天发的代码中有一处小错误,已通过留言的方式进行了纠正,详情请见【详解Python列表推导式】 lambda表达式常用来声明匿名函数,即没有函数名字的...

37490

扫码关注云+社区

领取腾讯云代金券