Problem description

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:

Input: [1,3,5,6], 5

Output: 2

Example 2:

Input: [1,3,5,6], 2

Output: 1

Example 3:

Input: [1,3,5,6], 7

Output: 4

Example 4:

Input: [1,3,5,6], 0

Output: 0

Solution 1: traverse the array

This problem is simple, one solution is to traverse the array, if the value at index i is greater then or equal to the target, then return i. Otherwise, if no element is bigger then the target, then return the length of the array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int len = nums.size();
if (len == 0){
return 0;
}
for (int i = 0; i < len; i++){
if (nums[i] >= target) {
return i;
}
else if(i == len-1 && nums[i] < target)
return len;
}
}
};

Solution 2: STL

In face, STL already provides the function used to find an insertion position in a sorted array. It is implemented using binary search.

1
2
3
4
5
6
7
#include <algorithm>
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
return lower_bound(nums.begin(), nums.end(), target) - nums.begin();
}
}

Binary search requires the input must be a sorted array. For list, binary search could not be possible.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int low = 0;
int high = nums.size() - 1;

while(low <= high){
int mid = low + (high - low) / 2;
if (nums[mid] == target)
return mid;
else if(nums[mid] < target)
low = mid + 1;
else
high = mid - 1;
}
return low;
}
};