35. Search for insertion location

Title description:

Given a sorted 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 the position where it will be inserted in order.

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

Example 1:
Input: [1,3,5,6], 5 output: 2Copy the code
Example 2:
Input: [1,3,5,6], 2 Output: 1Copy the code
Example 3:
Input: [1,3,5,6], 7 output: 4Copy the code
Example 4:
Input: [1,3,5,6], 0 output: 0Copy the code

Directions: For this part,

So let’s first look at the requirements of this problem, which is pretty straightforward, which is the most common binary search. Generally speaking, see sorted array we can consider using binary search method to achieve, here provides binary search method and brute force cracking code implementation, easier to understand. When writing code, be aware of the different meanings of the left and right boundaries to avoid errors in the loop.

Binary search solution:

func searchInsert(nums []int, target int) int { left := 0 right := len(nums) for left < right { middle := (right + left) / 2 if nums[middle] >= target  { right = middle } else { left = middle + 1 } } return left }Copy the code

Brute force cracking solution to achieve:

func SearchInsert(nums []int, target int) int {
	for i := 0; i < len(nums); i++ {
		if target <= nums[i] {
			return i
		}
	}
	return len(nums)
}
Copy the code

Conclusion:

In addition to this 35. Search insert position, similar binary search ideas of the topic is 34. Find the first and last position and finger of the element in the sorted array Offer 11. Rotate the smallest number of array, binary search method of the nature of the title is half search, according to the conditions each time can reduce half of the search scope, as long as find to meet such conditions. So what you need to pay attention to in this type of problem is under what circumstances the extreme value will satisfy the bar on the left and right boundary, and then pay attention to the problem limit and remove the duplicate result, and you can solve the problem. Interested partners can try to do the other questions above.