leetcode解题: Search Insert Position (35)

发表于 | 分类于

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.

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

解法1：Binary Search O(NLogn)

因为是sorted， 用binary search很容易解决。要注意的是最后判断nums[start], nums[end]的时候如果都没有符合的，那么说明要插入的位置是array的尾巴，要返回的结果是end+1， 比如
searchInsert([0],1)这样的情况。
C++

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

Java

1