搜索插入位置

题意

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

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

样例

[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 的情况。

代码实现

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
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:搜索插入位置

坚持原创技术分享,您的支持将鼓励我继续创作!