二分问题的基本思想及其实现（python3）

核心思想：

减而治之（逐渐缩小问题规模）。我们总是在区间[left..right]里查找元素目标。

（注意是左闭右闭区间。为什么不是「左闭右开」呢？「左闭右开」当然可以，但是我们不想把精力花在「右边界是不是可以取到」这件事情上，并且任意一个「左闭右开」区间一定唯一对应一个「左闭右闭」区间，所以到底是开区间还是闭区间，保持一致就可以。根据 mid 位置是不是目标元素，进而判断 mid 的左边是。）

基本思路：

根据待搜索区间里的中间元素 nums[mid] 与 target 的值的大小关系，判断下一轮搜索需要在哪个区间里查找，进而设置 left 和 right 的值。分为如下三种情况：

如果 nums[mid] == target，运气很好，找到了目标元素，返回 mid ；

如果 nums[mid] > target，说明 mid 以及 mid 的右边的所有元素一定都比 target 大，下一轮搜索需要在区间 [left..mid - 1] 里查找，此时设置 right = mid - 1；

如果 nums[mid] < target，说明 mid 以及 mid 的左边的所有元素一定都比 target 小，下一轮搜索需要在区间 [mid + 1..right] 里查找，此时设置 left = mid + 1。

把待搜索区间分成两个部分：

这个地方我起初没有理解，后来我悟了。这部分才是关键啊。

我们考虑区间的完整性，所以mid肯定只能在左右两个区间中的一个：

情况1：mid被分到左区间，区间变成[left,mid] 和 [mid+1,right]

情况2：mid被分到右区间，区间变成[left,mid-1] 和 [mid,right]

循环结束条件：

退出循环的时候，说明区间里不存在目标元素，返回 -1。那么循环结束的条件的是什么？

while (left < right)

在上面把待搜索区间分成两个部分的划分下，退出循环以后一定会有 left == right 成立，因此我们在退出循环以后，就不需要考虑到底返回 left 还是返回 right。

介绍一个比较好的经验：

我们在写判断条件时，通常把容易想到的，不容易出错的逻辑写在 if 的里面，这样就把复杂的、容易出错的情况放在了 else 的部分。

实现：

我们结合上面的思想来做一道题：

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

本题目要求我们找到第一个大于等于target的元素的位置，那么不容易出错的就是：小于target的元素就不是我们想要寻找的答案。所以我们可以这样写if语句：

if（nums[mid]<target):
    //下一轮搜索区间就是[mid+1, right]
    left = mid + 1

剩余的情况放在else中：

else:
    //下一轮搜索区间是[left, mid]
    right = mid

所以这道题的答案很显然了

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
    	n = len(nums)
    	l,r = 0, n-1

    	# 特殊判断 
    	if nums[n-1] < target:
    		return n

    	# 确保target<=nums[len-1]
    	while(l<r):
    		m = l + (r - l)//2
    		if nums[m] < target:
    			l = m + 1
    		else:
    			r = m
    	return l

参考文章：

https://leetcode-cn.com/problems/search-insert-position/solution/te-bie-hao-yong-de-er-fen-cha-fa-fa-mo-ban-python-/