「力扣」第 35 题:搜索插入位置(简单)


「力扣」第 35 题:搜索插入位置(简单)

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

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

示例 1:

输入: [1, 3, 5, 6], 5
输出: 2

示例 2:

输入: [1, 3, 5, 6], 2
输出: 1

示例 3:

输入: [1, 3, 5, 6], 7
输出: 4

示例 4:

输入: [1, 3, 5, 6], 0
输出: 0

分析:要找到大于或者等于 target 的第 1 个元素的下标,因此严格小于 target 的元素就不是解。根据这一点写出代码。

Java 代码:

public class Solution {

    public int searchInsert(int[] nums, int target) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }

        if (nums[len - 1] < target) {
            return len;
        }
        int left = 0;
        int right = len - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            // 当 nums[mid] 严格小于目标元素时,不是解
            if (nums[mid] < target) {
                // 下一轮搜索的区间 [mid + 1, right]
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

文章作者: liweiwei1419
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 liweiwei1419 !
评论
 上一篇
「力扣」第 69 题:x 的平方根(简单) 「力扣」第 69 题:x 的平方根(简单)
「力扣」第 69 题:x 的平方根(简单) 链接 实现 int sqrt(int x) 函数。 计算并返回 x 的平方根,其中 x 是非负整数。 由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。 示例 1: 输入:4 输出:
下一篇 
「力扣」第 23 题:合并 K 个排序链表(困难) 「力扣」第 23 题:合并 K 个排序链表(困难)
「力扣」第 34 题:排序数组查找首、末位置(简单) 链接 题解链接(含视频题解) 给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。 你的算法时间复杂度必须是 $O(\l
  目录