35. 搜索插入位置

  |   0 评论   |   0 浏览

来源力扣(LeetCode)
难度:简单

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

示例 1

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

示例 2

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

示例 3

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

示例 4

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

题解

方法一:遍历查找

 1class Solution {
 2   public int searchInsert(int[] nums, int target) {
 3        // target比数组中的所有元素都大
 4        if (target > nums[nums.length - 1]) {
 5            return nums.length;
 6        }
 7
 8        int i = 0;
 9        for (; i < nums.length; i++) {
10            if (nums[i] >= target) {
11                break;
12            }
13        }
14        return i;
15    }
16}

方法二:二分查找

 1class Solution {
 2    public int searchInsert(int[] nums, int target) {
 3        int lt = 0;
 4        int rt = nums.length -1;
 5
 6        while (lt < rt) {
 7            int mid = lt + (rt - lt)/2;
 8            if (nums[mid] < target) {
 9                lt = mid + 1;
10            } else {
11                rt = mid;
12            }
13        }
14
15        if (nums[lt] < target) {
16            return lt + 1;
17        }
18
19        return lt;
20    }
21}