Search Insert Position

Question

Problem Statement

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.

Example

[1,3,5,6], 5 → 2

[1,3,5,6], 2 → 1

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

[1,3,5,6], 0 → 0

O(log(n)) time

题解

Python

class Solution:
"""
@param A : a list of integers
@param target : an integer to be inserted
@return : an integer
"""
def searchInsert(self, A, target):
if not A:
return 0
st, ed = 0, len(A) - 1
while st + 1 < ed:
mid = (st + ed) / 2
if A[mid] == target:
ed = mid
elif A[mid] < target:
st = mid
else:
ed = mid
if A[st] >= target:
return st
elif A[ed] >= target:
return ed
else:
return len(A)


C++

class Solution {
/**
* param A : an integer sorted array
* param target :  an integer to be inserted
* return : an integer
*/
public:
int searchInsert(vector<int> &A, int target) {
if (A.empty()) return 0;

int n = A.size();
int lb = -1, ub = n;
while (lb + 1 < ub) {
int mid = lb + (ub - lb) / 2;
if (A[mid] < target) {
lb = mid;
} else {
ub = mid;
}
}
return ub;
}
};


Java

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) {
if (A == null || A.length == 0) {
return -1;
}

int start = -1, end = A.length;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (A[mid] == target) {
return mid; // no duplicates
} else if (A[mid] < target) {
start = mid;
} else {
end = mid;
}
}

return start + 1;
}
}


源码分析

1. 目标值在数组范围之内，最后返回值一定是start + 1
2. 目标值比数组最小值还小，此时start 一直为-1, 故最后返回start + 1 也没错，也可以将-1 理解为数组前一个更小的值
3. 目标值大于等于数组最后一个值，由于循环退出条件为start + 1 == end, 那么循环退出时一定有start = A.length - 1, 应该返回start + 1