前言
二分法是典型的搜索算法，其主要运用于有序序列中寻找目标值。其思路非常简单，就是不断比较搜索区间的中间值与目标值，当中间值等于目标值则结束搜索，如果中间值大于目标值，则继续搜索左半区间，反之搜索右半区间。
总结下，二分法就是在搜索过程中不断地将搜索区间减半，直到搜索到目标值或者搜索区间为空集。
实践
二分法的思路很简单，只要按照前面描述即可实现。那为何我们还要去学习掌握呢？
那是因为二分法看起来非常简单，但是却非常考验细节，我们称其为细节魔鬼也不为过。下面我们通过leetcode真题来学习。
leetcode-704 二分查找
我们先来个最简单的二分查找
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。（nums无重复）
const search = function(nums, target) { // 初始区间 let left = 0 let right = nums.length - 1 // 结束条件 [right, left]搜索区间为空 while(right >= left) { // 中间值 // 注意区分 Math.floor((right + left) / 2) 的写法 // 这种写法可以保证不会出现整数溢出 const mid = left + Math.floor((right - left) / 2) // 等于目标值返回 if (nums[mid] === target) return mid // 大于目标值收缩右区间 // 注意mid已经被搜索过了 // 所以是mid-1 if (nums[mid] > target) { right = mid - 1 } // 小于目标值收缩左区间 // 同理mid+1 if (nums[mid] < target) { left = mid + 1 } } // 没有目标值返回-1 // 前提是我们搜索条件是 right >= left // 可以保证已经搜索完所有元素 return -1 }; 复制代码
看我写完感觉不难，但是如果自己动手写呢？
我们来改变下搜索的结束条件，将 right >= left 改为 right > left
const search = function(nums, target) { let left = 0 let right = nums.length - 1 // 结束条件更改为 [left, left] 此时还剩下唯一值未经搜索 while(right > left) { const mid = left + Math.floor((right - left) / 2) if (nums[mid] === target) return mid if (nums[mid] > target) { right = mid - 1 } if (nums[mid] < target) { left = mid + 1 } } // 相应需要对比剩余值和目标值完成搜索 return nums[left] === target ? left : -1 }; 复制代码
leetcode-35 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。（nums无重复）
const searchInsert = function(nums, target) { let left = 0 let right = nums.length - 1 let ans = null // 我们保持结束条件不变 while(left <= right) { const mid = left + Math.floor((right - left) / 2) // 返回目标值索引 if (nums[mid] === target) return mid if (nums[mid] > target) { // 我们在这引入新变量来存储位置 // 实际将更新为第一个大于目标值的元素索引 ans = mid right = mid - 1 } if (nums[mid] < target) { left = mid + 1 } } // 返回插入位置 return ans }; 复制代码
leetcode-34 在排序数组中查找元素的第一个和最后一个位置
我们再来看看如何搜索边界值吧
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。
我们先来看看如何搜索左边界吧
const searchLeft = function(nums, target) { let left = 0 let right = nums.length - 1 // 同样我们引入变量来存储位置 let first = -1 while(left <= right) { const mid = left + Math.floor((right - left) / 2) if (nums[mid] === target) { // 当元素值和目标值相等的时候 // 我们存储当前索引并缩减右区间 // 这样可以让我们有机会往左搜索左边界 first = mid right = mid - 1 } if (nums[mid] > target) { right = mid - 1 } // 这部分保持不变 // 只要搜索值小于目标值才会更新left值 // 可以保证left始终小于左边界或者等于左边界 // 如果等于左边界也不用担心 // 因为此索引会在我们所减右区间时被搜索 if (nums[mid] < target) { left = mid + 1 } } } // 此时first变是左边界或者保持为-1 return first 复制代码
同理，搜索右边界的代码也是一样的
const searchRight = function(nums, target) { let left = 0 let right = nums.length - 1 let last = -1 while(left <= right) { const mid = left + Math.floor((right - left) / 2) if (nums[mid] === target) { // 唯一的改变点就是此时缩减左区间 // 以此达到往右到右边界的目的 last = mid left = mid - 1 } if (nums[mid] > target) { right = mid - 1 } if (nums[mid] < target) { left = mid + 1 } } } return last 复制代码
以搜索左边界为例，我们来试试改变搜索结束条件后的代码
const searchLeft = function(nums, target) { let left = 0 let right = nums.length - 1 // 我们改变结束条件为left<right // 也就是结束后剩下[left,left]未搜索 while(left < right) { const mid = left + Math.floor((right - left) / 2) // 当搜索值大于目标值时我们缩减右区间 // 此时的区别在于更新右区间为mid而非mid-1 // 这边实际和搜索结束条件是有联系的 // 如果搜索条件为left<=right有可能导致搜索区间缩减为[right,right]后陷入死循环 if (nums[mid] >= target) { right = mid } if (nums[mid] < target) { left = mid + 1 } } } // 同样的我们需要完成最后一个值的搜索 return nums[left] === target ? left : -1 复制代码
算法公式
通过前面的题我们可以总结出一套常用的二分法公式
const search = (nums, target) => { let left = 0 let right = nums.length - 1 // 有时候也可以是left<right // 如果可以的话 // 我们尽量设置为left<=right完成全区间搜索 // 也方便统一 while(left <= right) { const mid = left + Math.floor((right - left) / 2) if (nums[mid] === target) { // ... } if (nums[mid] > target) { // ... } if (nums[mid] < target) { // ... } } return // ... } 复制代码
总结
今天我们通过三道经典题来掌握二分法，实际二分法还有很多其他的题型。虽然公式是大致相同的，但是其中的细节，包括初始边界，结束条件，以及循环体内的区间缩减都是很考验大家的。
