二分查找法的原理描述（算法套路三:二分查找——红蓝染色法）
算法套路三:二分查找——红蓝染色法
套路示例：LeetCode34. 在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums ，和一个目标值 target 。请你找出给定目标值在数组中的开始位置和结束位置 。如果数组中不存在目标值 target ，返回 [-1, -1] 。你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题 。
二分查找本身并不复杂 ，但在写代码时往往会出现问题 ，比如出现死循环 ，不知道如何初始化 ，不知道为什么有时left=mid ，有时left=mid+1 ，有时会莫名其妙把某个数排除 ，那么看完这个套路课你都懂了
首先是循环不变量
以示例一为例：
L和R分别指向询问的左右边界 ，即闭区间[L, R]M指向当前正在询问的数
蓝色背景表示 true ，即≥target
红色背景表示false ，即
白色背景表示不确定right 左移使右侧变蓝 (判断条件为 true ) left 右移使左侧变红 (判断条件为 false )
闭区间时 ，L-1必定是红色即false ，R+1必定是蓝色即true ，这就是循环不变量二分查找分三种写法 ，分别是：
闭区间写法
# lower_bound 返回最小的满足 nums[i] >= target 的 i # 如果数组为空 ，或者所有数都 < target ，则返回 len(nums) # 要求 nums 是非递减的 ，即 nums[i] <= nums[i + 1] # def lower_bound(nums: List[int], target: int) -> int: left, right = 0, len(nums) - 1 # 闭区间 [left, right] while left <= right: # 区间不为空 # 循环不变量：left-1与right+1 # nums[left-1] < target # nums[right+1] >= target mid = (left + right) // 2 if nums[mid] < target: left = mid + 1 # 范围缩小到 [mid+1, right] else: right = mid - 1 # 范围缩小到 [left, mid-1] return left # 或者 right+1 class Solution: def searchRange(self, nums: List[int], target: int) -> List[int]: start = lower_bound(nums, target) # 选择其中一种写法即可 if start == len(nums) or nums[start] != target: return [-1, -1] # 如果 start 存在 ，那么 end 必定存在 end = lower_bound(nums, target + 1) - 1 return [start, end]左闭右开区间写法
def lower_bound2(nums: List[int], target: int) -> int: left = 0 right = len(nums) # 左闭右开区间 [left, right) while left < right: # 区间不为空 # 循环不变量：left-1与right # nums[left-1] < target # nums[right] >= target mid = (left + right) // 2 if nums[mid] < target: left = mid + 1 # 范围缩小到 [mid+1, right) else: right = mid # 范围缩小到 [left, mid) return left # 或者 right开区间写法
def lower_bound3(nums: List[int], target: int) -> int: left, right = -1, len(nums) # 开区间 (left, right) while left + 1 < right: # 区间不为空 mid = (left + right) // 2 # 循环不变量：left与right # nums[left] < target # nums[right] >= target if nums[mid] < target: left = mid # 范围缩小到 (mid, right) else: right = mid # 范围缩小到 (left, mid) return right # 或者 left+1 有序数组中二分查找的四种类型（下面的转换仅适用于数组中都是整数） ，lower_bound返回下标 第一个大于等于x的下标： low_bound(x) 第一个大于x的下标：可以转换为第一个大于等于 x+1 的下标 ，low_bound(x+1) 最后一个一个小于x的下标：可以转换为数组中第一个大于等于 x 的下标 的左边位置, low_bound(x) - 1; 最后一个小于等于x的下标：可以转换为数组中第一个大于等于 x+1 的下标 的 左边位置, low_bound(x+1) - 1;套路总结
红蓝染色法
left指针掌管左边蓝色区域 ，蓝色表示 truej即所求值及其右侧 ，right指针掌管右边红色区域 ，红色表示false即所求值左侧 ，两者互不冲突 ，通过不断向目标区域靠近 ，扩大两个指针的掌管区域 ，直到两者掌管的区域接壤 使用闭区间时 ，L-1必定是红色即false ，R+1必定是蓝色即true ，这就是循环不变量 关键不在于区间里的元素具有什么性质 ，而是区间外面的元素具有什么性质 ，即将区间外染成红色与蓝色 。 根据以上两点 ，在做题时关键即确定二分条件函数isBlue() ，判断是否满足条件 ，满足条件则right 左移使右侧变蓝 ，不满足条件则left 右移使左侧变红代码规范
注意代码区间开闭写法 ，之前提过的在LeetCode题解中大家看到的left与right取初值有时不一样 ，在二分时left指针有时等于mid+1有时等于mid ，这是区间开闭的问题 ，不必纠结太多 ，三种都可以 ，我习惯于使用闭区间
如果找不到比较元素 ，则可将数组最后一个元素单独提出作为比较元素 ，且right=n-2 ，因为若最后一个元素为所查找元素 ，二分查找时left也可以超出right=n-2的范围找到该元素；若不是所查找元素 ，单独提出也没有影响.
根据上一点就明白为什么有时LeetCode题解在二分前就去掉了数组某个元素 ，这不会影响最终结果 ，可能是因为能判断这个元素不是所求结果 ，或者这个结果在最后一次循环时能够遍历到（闭区间时left能够遍历到数组长度+1）
练习LeetCode162. 寻找峰值
峰值元素是指其值严格大于左右相邻值的元素 。
给你一个整数数组 nums ，找到峰值元素并返回其索引 。数组可能包含多个峰值 ，在这种情况下 ，返回 任何一个峰值 所在位置即可 。你可以假设 nums[-1] = nums[n] = -∞ 。你必须实现时间复杂度为 O(log n) 的算法来解决此问题 。对于所有有效的 i 都有 nums[i] != nums[i + 1]
已知nums[i] != nums[i + 1] ，那么我比较nums[i] 与nums[i + 1] ，且将最后一个元素提出 ，防止nums[i + 1]数组越界 ，而若该元素是峰值 ，left在最后一次循环时能是left=n-1找到 ，若不是峰值 ，则不需要遍历该元素
func findPeakElement(nums []int) int { left:=0 right:=len(nums)-2 for left<=right{ mid:=left+(right-left)/2 if nums[mid]<nums[mid+1]{ left=mid+1 }else{ right=mid-1 } } return left }练习LeetCode153. 寻找旋转排序数组中的最小值
已知一个长度为 n 的数组 ，预先按照升序排列 ，经由 1 到 n 次 旋转 后 ，得到输入数组 。例如 ，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次 ，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次 ，则可以得到 [0,1,2,4,5,6,7]
注意 ，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组 ，并按上述情形进行了多次旋转 。请你找出并返回数组中的 最小元素 。你必须设计一个时间复杂度为 O(log n) 的算法解决此问题 。
我们考虑数组中的最后一个元素 x即nums[len-1]：在最小值右侧的元素 ，它们的值一定都小于等于 x；而在最小值左侧的元素 ，它们的值一定都大于等于 x,通过与最后一个元素x比较 ，可以知道是前半段还是后半段升序数组 。
如果nums[mid]>nums[n-1] ，那么mid指向最小值左边 ，即最小值在mid右边 ，故去掉左半边 ，left=mid+1
如果nums[mid]<nums[n-1] ，那么mid指向最小值右边 ，即最小值在mid左边 ，故去掉右半边 ，right=mid-1 func findMin(nums []int) int { n:=len(nums) l,r:=0,n-2 for l<=r{ mid:=l+(r-l)/2 if nums[mid]>nums[n-1]{ l=mid+1 }else{ r=mid-1 } } return nums[l] }进阶LeetCode154. 寻找旋转排序数组中的最小值 II
已知一个长度为 n 的数组 ，预先按照升序排列 ，经由 1 到 n 次 旋转 后 ，得到输入数组 。例如 ，原数组 nums =
[0,1,4,4,5,6,7] 在变化后可能得到： 若旋转 4 次 ，则可以得到 [4,5,6,7,0,1,4] 若旋转 7 次 ，则可以得到
[0,1,4,4,5,6,7] 注意 ，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组
[a[n-1], a[0], a[1], a[2], …, a[n-2]] 。 给你一个可能存在 重复 元素值的数组 nums
，它原来是一个升序排列的数组 ，并按上述情形进行了多次旋转 。请你找出并返回数组中的 最小元素 。你必须尽可能减少整个过程的操作步骤 。这道题与LeetCode 153寻找旋转排序数组中的最小值 类似 ，但 nums 可能包含重复元素 。前两种情况与上一题一样 ，
第三种情况是 nums[mid]==nums[high-1] 。如下图所示 ，由于重复元素的存在 ，并不能确定 nums[pivot] 究竟在最小值的左侧还是右侧 ，不能随意二分 。但它们的值相同 ，所以无论nums[high] 是不是最小值 ，都有一个它的「替代品」nums[pivot] 。因此我们可以忽略二分查找区间的右端点 ，即high-- 。
如下图中随着high不断减少 ，必会使得 nums[mid]>nums[high] ，此时即可继续二分
func findMin(nums []int) int { left, right := 0, len(nums)-2 for left <= right { mid := left + (right-left)/2 if nums[mid] < nums[right+1] { // 蓝色 right = mid-1 } else if nums[mid] > nums[right+1] { // 红色 left = mid+1 } else { right-- } } return nums[left] }进阶LeetCode33. 搜索旋转排序数组
整数数组 nums 按升序排列 ，数组中的值 互不相同 。在传递给函数之前 ，nums 在预先未知的某个下标 k（0 <= k <
nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], …, nums[n-1],
nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数） 。例如 ， [0,1,2,4,5,6,7]
在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。给你 旋转后 的数组 nums 和一个整数 target ，如果 nums
中存在这个目标值 target ，则返回它的下标 ，否则返回 -1 。你必须设计一个时间复杂度为 O(log n) 的算法解决此问题 。创心域SEO版权声明：以上内容作者已申请原创保护，未经允许不得转载，侵权必究！授权事宜、对本内容有异议或投诉，敬请联系网站管理员，我们将尽快回复您，谢谢合作！