算法基本型——二分

引言

我还记得在高中的时候，有一道数学题是这么说的：在一片森林中，有一只啄木鸟守护着所有树木的健康，但啄木鸟面对一棵树，如何快速找到害虫呢？

我脑海里第一反应：从上啄到下，不就找到害虫了吗？

数学老师似乎看出了我的想法，他说：啄木鸟比同学们聪明些，它先啄树干的中间，观察害虫的活动范围是在上面还是下面，如果是上面，于是它再去啄上面树干的中间。于是啄木鸟每次只需要关注树干的一半，效率大大提升。

当时稚嫩的我并不知道这其中蕴含的精妙算法，只知道题就是这么做的。多年后，当我接触到编程算法，我才意识到，啄木鸟原来也懂二分，万能的造物者啊。

1. 二分

二分是编程算法中最简单的一个算法，它思想十分朴素，就是每次只关注目标的一半，一半又划分为一半，每次都缩小1/2，那么刚好符合对数的形式，因此二分的时间复杂度为O(lgn) < O(n)。二分的使用有一个重要限定，那就是目标数组是有序的。

2. 二分基本型

比如我们需要在数组[2,4,6,8,9,12]中查找6，用二分代码如下：

	func search(nums []int, target int) int {
	    l, r := 0, len(nums)
	    for l < r {
            mid := l + ((r - l) >> 1) // 这里请大家注意，请用这种方式来二分
	        if nums[mid] == target {
	            return mid
	        }
	        if nums[mid] > target {
	            r = mid
	        } else {
	            l = mid + 1
	        }
	    }
	    return -1
	}

这就是二分的基本型，也称为标准二分。我们来分析一下。l < r ，说明这是左闭右开，左闭右闭可以吗？当然可以，对应代码如下：

	func search(nums []int, target int) int {
	    l, r := 0, len(nums)-1
	    for l <= r {
	        mid := l + ((r - l) >> 1) // 这里请大家注意，请用这种方式来二分
	        if nums[mid] == target {
	            return mid
	        }
	        if nums[mid] > target {
	            r = mid - 1
	        } else {
	            l = mid + 1
	        }
	    }
	    return -1
	}

这同样是标准二分。我们来观察一下对应关系：

左闭右开

变量	初始值	过程值	判断条件
l	0	mid + 1	l < r
r	len(nums)	mid

左闭右闭

变量	初始值	过程值	判断条件
l	0	mid + 1	l <= r
r	len(nums)-1	mid - 1

聪明的你应该能体悟到这之间的对应关系。那么这就是二分的基本型。请大家记住这两个固定的关系。

二分细节很复杂，哪里-1，哪里+1？细节是魔鬼，但是我们不用去玩弄那些细节，请记住基本型，我们所有的解题都基于基本型。

3. 二分基本型的应用

3.1. 二分找边界

二分更多的应用是用来找边界，题目LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置

找左边界：

func findLeftEdge(nums []int, target int) int {
	l, r := 0, len(nums)-1 
	for l <= r { 
		mid := l + ((r - l) >> 1) 
		if nums[mid] == target {
			r = mid - 1 // 收紧右边界，目标更靠近左边界
		} else if nums[mid] < target {
			l =  mid + 1
		} else {
			r = mid - 1
		}
	}
	// 返回左边界
	return l
}

查右边界

func findRightEdge(nums []int, target int) int {
	l, r := 0, len(nums)-1 
	for l <= r { 
		mid := l + ((r - l) >> 1) 
		if nums[mid] == target {
			l = mid + 1 // 收紧左边界，目标更靠近右边界
		}else if nums[mid] < target {
			l =  mid + 1
		}else {
			r = mid - 1
		}
	}
	// 返回右边界
	return r
}

可以很清楚的看到，我们查询边界没有做很复杂的改动，都是基于我们的基本型来的。所以基本型要牢记于心。该题题解如下：

func searchRange(nums []int, target int) []int {
	l := findLeftEdge(nums, target)
	// 越界 或 目标值不存在，直接返回
	if l == len(nums) || nums[l] != target {
		return []int{-1,-1}
	}
	r := findRightEdge(nums, target)
	return []int{l, r}
}

// 寻找左边界
func findLeftEdge(nums []int, target int) int {
	l, r := 0, len(nums)-1 
	for l <= r { 
		mid := l + ((r - l) >> 1) 
		if nums[mid] == target {
			r = mid - 1 // 收紧右边界，目标更靠近左边界
		}else if nums[mid] < target {
			l =  mid + 1
		}else {
			r = mid - 1
		}
	}
	// 返回左边界
	return l
}

// 寻找右边界
func findRightEdge(nums []int, target int) int {
	l, r := 0, len(nums)-1 
	for l <= r { 
		mid := l + ((r - l) >> 1) 
		if nums[mid] == target {
			l = mid + 1 // 收紧左边界，目标更靠近右边界
		}else if nums[mid] < target {
			l =  mid + 1
		}else {
			r = mid - 1
		}
	}
	// 返回右边界
	return r
}

3.2. 二分找峰值

请看LeetCode 162. 寻找峰值

我这边直接给出题解：

func findPeakElement(nums []int) int {
	l, r := 0, len(nums)-1
	for l <= r {
		mid := l + ((r - l) >> 1)
		// 收紧右边界，目标更靠近左边界
		if mid + 1 < len(nums) && nums[mid] == nums[mid+1] {
			r = mid - 1
		// 向右爬坡
		} else if mid + 1 < len(nums) && nums[mid] < nums[mid+1] {
			l = mid + 1
		// 向左爬坡
		} else {
			r = mid - 1
		}
	}
	return l
}

可以看到，我们依然是基于二分基本型来解题的。唯一不同的是，我们比较的目标是nums[mid+1]，nums[mid] < nums[mid+1]向右爬坡，nums[mid] > nums[mid+1]向左爬坡，这个过程是不是就像爬坡一样。

3.3. 旋转数组

请看LeetCode 153. 寻找旋转排序数组中的最小值

我这边直接给出题解：

func findMin(nums []int) int {
    l, r := 0, len(nums)-1
	for l <= r {
		mid := l + ((r - l) >> 1)
		// 收紧右边界，目标更靠近左边界
		if nums[mid] == nums[len(nums)-1] {
			r = mid - 1
		// 向左下坡
		} else if nums[mid] < nums[len(nums)-1] {
            r = mid - 1
		// 向右爬坡
		} else {
            l = mid + 1
		}
	}
	return nums[l]
}

可以看到，我们还是基于二分基本型来解题的。不同的是，我们比较的目标是nums[len(nums)-1]，nums[mid] < nums[len(nums)-1]向左下坡，nums[mid] > nums[len(nums)-1]向右爬坡，这里就是与找峰值的区别所在，就决定了我们的目标是比较nums[len(nums)-1]而不是nums[mid+1]。这个过程大家仔细去分析下程序就明白了。

4. 二分基本型扩展应用

那掌握基本型是不是就完了？不不不。

上面的题目都是直接给我们数组，我们对着数组就是二分。有难度的题目会那么明显让我们看出二分的意图吗？要有那么简单的话，世界就充满爱了。

我们直接上题：LeetCode 剑指 Offer II 073. 狒狒吃香蕉

请大家好好体味一下这道题，然后再来看题解。

func minEatingSpeed(piles []int, h int) int {
    sort.Ints(piles)
    l, r := 1, piles[len(piles)-1]
    for l <= r {
        mid := l + ((r - l) >> 1)
        if judge(piles, mid) == h {
            r = mid - 1
        }
        if judge(piles, mid) > h {
            l = mid + 1
        } else {
            r = mid - 1
        }
    }
    return l
}

func judge(piles []int, mid int) int {
    res := 0
    for i := 0; i < len(piles); i++ {
        res += piles[i] / mid
        if piles[i] % mid != 0 {
            res++
        }
    }
    return res
}

现在大家能明白了吧，我们要二分的数组是[1, piles[len(piles)-1]]，它是隐藏的，需要我们自己挖掘。题目往往难点就在这里，需要通过分析题目后找出隐藏目标。