35. Search Insert Position

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:**

1
2
Input: [1,3,5,6], 5
Output: 2
**Example 2:**
1
2
Input: [1,3,5,6], 2
Output: 1
**Example 3:**
1
2
Input: [1,3,5,6], 7
Output: 4
**Example 4:**
1
2
Input: [1,3,5,6], 0
Output: 0
思路:遍历数组,为目标数字找到合适的位置。代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
static const auto ___ = []()
{
ios::sync_with_stdio(false);
cin.tie(0);
return 0;
}();
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {

if (nums.size() == 0) return 0;
if (nums[nums.size() - 1] < target) return nums.size();
//if (nums[nums.size() - 1] == target) return nums.size() - 1;
if (nums[0] >= target) return 0;

for (int i = 0; i < nums.size() - 1; i++) {
if (nums[i] < target && nums[i + 1] >= target) return i+1;
}
}
};
没有加神奇代码时,Runtime 4ms,Ranking 99.8%。采用神奇代码后,Runtime 0ms,Ranking 100%. 突然发现可以用二分法来做,能大大的减少时间。看了一下排名第一的算法,也是用二分法,可能测试用例太少的原因,没有跟其他算法区分开。代码如下. copy~~~~
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
31
32
33
34
static const auto ___ = []()
{
ios::sync_with_stdio(false);
cin.tie(0);
return 0;
}();

class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
if (nums.size() == 0) return 0;

int x = 0;
int y = nums.size();
int mid = (x+y)/2;


if (nums[x] > target) return 0;

if (nums[y-1] < target) return y;

while(x <= y) {
if (nums[mid] == target) return mid;

if (nums[mid] < target) x = mid + 1;

if (nums[mid] > target) y = mid - 1;

mid = (x+y)/2;
}

return x;
}
};