【LeetCode】第35题 搜索插入位置(二分查找)

题目:搜索插入位置

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

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

示例 1:

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

示例 2:

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

示例 3:

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

示例 4:

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

解法1:直接暴力遍历搜索

由于数组已经排序,从头遍历数组,判断大小,当索引指向位置的元素大于等于目标值时,则返回当前索引。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public int searchInsert(int[] nums, int targer) {
if(target == 0 || nums.length == 0 || target <= nums[0]) {
return 0;
}

int len = nums.length;
for(int i = 0; i < len; i++) {
if (nums[i] >= target) {
return i;
}
}
}
}

解法2:二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*
* @lc app=leetcode.cn id=35 lang=java
*
* [35] 搜索插入位置
* √ Accepted
* √ 62/62 cases passed (0 ms)
* √ Your runtime beats 100 % of java submissions
* √ Your memory usage beats 88.75 % of java submissions (37.4 MB)
*/
class Solution {
public int searchInsert(int[] nums, int targer) {
if(target == 0 || nums.length == 0 || target <= nums[0]) {
return 0;
}

int start = 0;
int end = nums.length;
int middle;
while(start <= end) {
middle = ((end - start) >> 1) + start;
if (nums[middle] > target) {
start = middle - 1;
} else {
end = middle;
}
}

return middle;
}
}
您的支持将让服务器运行更长久