# Search for insertion position

2020-12-06 09:02:12

# Search insert location （easy）

A better reading experience should be ：

1. Examine the subject - reflection
3. Arrangement - inductive

## One 、 subject

LeetCode Topic link ：35. Search for the insertion location

Given a sort array and a target value , Find the target value in the array , And return its index . If the target value does not exist in the array , Return to where it will be inserted in sequence .

You can assume that there are no duplicate elements in the array .

Example 1:

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

Example 2:

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

#### Analyze the problem stem

It's important to analyze the topic , Every time I read the topic, I should thank you for reading comprehension , In this question , We learned that ：

1. An array is an ordered array
2. No repeating elements

#### Answer 1 （ Violence law ）

When it comes to the law of violence , It's the frequent use of traversal , And there's no such thing as “ tricks ”, From top to bottom, it's all real ！

Time complexity ：O(n)
Spatial complexity ：O(1)

Ideas

• Find the first match target Big elements , Its subscript , It's the answer .

Realization

var searchInsert = function(nums, target) {

const len = nums.length;
for (let i = 0; i < len; i++) {

if (nums[i] >= target) {

return i;
}
}
return len;
};

#### Explanation 2 （ Dichotomy ）

Find in a sorted array , We can use Dichotomy

Here's what we're trying to do ： Find a subscript index, We were looking for it nums[index] <= target First value of .

If you can't find it , The length of the array is returned

Time complexity ：O(log(n))
Spatial complexity ：O(1)

var searchInsert = function(nums, target) {

const len = nums.length;
let left = 0; // Left boundary
let right = len - 1; //  Right border
let ans = len; //  Return value , Note that if the target is not in the array , Returns the length of the array
while (left <= right) {

mid = ((right - left) >> 1) + left;
if (target <= nums[mid]) {

//  Prove that the left boundary is inside the array
ans = mid; //  Update return value
right = mid - 1;
} else {

left = mid + 1;
}
}
return ans;
};

## 3、 ... and 、 At the end

This is the first article on dichotomy , What does dichotomy do , And other scenarios I'll send out in a new chapter , Mutual encouragement

• flower ： Afterglow
• WX：j565017805
• addiction JS, Level co., LTD. , Learning with an open mind

Other precipitates

If you finally see , Let's have a three company company , This is the biggest encouragement for me ！

https://chowdera.com/2020/12/20201206085959973s.html