LeetCode35解题思路

2019年06月12日 |

leetcode/ algorithm/ easy

| algorithm

原题

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:

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

解题思路

由题目条件：

1. 有序数组
2. 无重复元素
   可得思路：
   二分法

我的凹糟二分法

二分法这个东西虽然很容易想出来，但是具体实现上我脑子感觉就是跟不上，自己写就是会写出一坨不正宗的二分法。

func searchInsert(nums []int, target int) int {
	e := len(nums)
	if e == 1 {
		if target <= nums[0] {
			return 0
		}
		return 1
	}
	s := 0
	t := []int{}
	m := 0
	for {
		m = (e-s)/2 + s
		if nums[m] > target {
			e = m
		} else {
			s = m
		}
		t = nums[s:e]
		if len(t) == 1 {
			break
		}
	}
	if target <= t[0] {
		return s
	}
	return e
}

我的这个思路的问题在于固定了起始s和结束e这两个变量，而且还不能兼容所有情况，所以不能算是真宗的二分法。

正确的实现在下面的代码里。

代码实现

Golang实现

https://github.com/cook-coder/my-leetcode-solution/tree/master/easy/35