对于二分题，其实就是设定一个两头值 mid, 而后通过这个值进行一个判断 check(mid)， 通过这个函数的返回值，判断将不可能的一半剪切掉；
在刷题的时候须要留神次要是两局部，check 函数的定义以及边界的抉择（等号的抉择，以及最初是 return left 还是 right）
这次次要是 LC 的二分专题，外面的简略题根本都是比拟显性的提醒了 check 函数的构建，比方说间接找出某个值，而难题个别都是 check 函数比拟难想的，这个时候就须要教训了；
狭义上只有是排好序（部分排序），只有是找某个值，大部分都能够思考用二分，这样复杂度能够升高很多；
对于边界，我的循环完结条件是 left <= right ， 因为如果要多记很多模板，怕会出问题，所以退出条件根本都按这个，而后无论是那种模块，都基于这个完结条件来判断，这样能够把问题膨胀都循环里的断定的 check 函数，多做了就会发现端倪；
而后对于退出之后 left 还是 right ，这个是具体问题具体分析；因为我的完结断定条件是 left<=right ，所以如果没用两头返回，那么必然存在 left === right 的时候，这个时候依据断定条件，就晓得 right 在 left 的后面，而到底是左迫近，还是右迫近，都比拟好判断了，因为这个时候曾经退出去了，left 和 right 所代表的 check 的状态也是不言而喻的，那么看题目要求什么，给什么即可；
对于二分，我感觉这个专题就根本足够了，简略居多，难题也有两个；如果是第一次学习二分，那么依照专栏的三个模板去记忆也 ok， 他人的教训终归是适宜他人本人，做题最重要是把握住本人的节奏，记忆本人最相熟的那个点，强行模拟他人反而落了下乘；
当然那个男人那么强，我的做题就是模拟的他，缓缓大佬的解法就是我本人的节奏了，毕竟模拟多了，其实就是本人的了，除了算法，其余的工程化学习也是一样的；
那么，周末高兴，下周开 dp 吧，毕竟这个听有意思的。
模板 1
- 目标值是一个固定的 target，在二分过程中须要一直的判断，如果胜利就返回对应的值，否则间接返回失败的值
- 返回值如果是向下取，返回 right，如果向上取，则返回 left，还有可能返回一个特定给的失败值；
var search = function (fn, target) { let left = 最小值, right = 最大值; while (left <= right) { // 取 mid 值 const mid = ((right - left) >> 1) + left; //这里的 fn 可能是函数，也可能只是数组取值，反正就是能够获得一个值去跟 target 比拟 const temp = fn(mid); if (temp === target) return mid; if (temp < target) { left = mid + 1; } else { right = mid - 1; } } return 没有准确匹配后的值;};704. 二分查找
var search = function (nums, target) { const len = nums.length; if (!len) return -1; let left = 0, right = len - 1; while (left <= right) { const mid = ((right - left) >> 1) + left; if (nums[mid] === target) return mid; if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1;};69. x 的平方根
// 69. x 的平方根var mySqrt = function (x) { let left = 0, right = x; while (left <= right) { const mid = ((right - left) >> 1) + left; const sqrt = mid * mid; if (sqrt === x) return mid; if (sqrt < x) { left = mid + 1; } else { right = mid - 1; } } // 向下取整 return right;};374. 猜数字大小
剖析
- 这里内置一个函数 guess(n), 返回值是 -1 0 1, -1 是 targt 值更小
var guessNumber = function (n) { let left = 1, right = n; while (left <= right) { const mid = ((right - left) >> 1) + left; if (guess(mid) === 0) return mid; if (guess(mid) > 0) { // 这个时候 mid < pick left = mid + 1; } else { right = mid - 1; } }};// 本人模仿一下这个 guess 函数吧 -- 假设第二个参数就是指标猜的数字，咱们能够用它来初始化，默认是5function guess(num, pick = 5) { if (num === pick) return 0; if (pick < num) return -1; if (pick > num) return 1;}441. 排列硬币
剖析
- 这里求的是一个左侧极值的二分法，是向右迫近的二分
- 累计值算法是小学数学题 sum = (first+end)*count/2
- 每次取中间层数，求出到这个层数须要的币数 sum，而后和目标值 n 比拟
- 如果刚好合乎，间接返回（这里能够膨胀到左侧断定条件中）；如果 count 比拟少，则 left 要提到 mid+1,否则 right 要提到 mid-1
- 因为最初要返回的是最迫近 n 的层数，所以判断一下当 left === right 状况，如果小于 n，则 left = mid+1，这个时候 right 符合要求，所以跳出循环后，返回的是 right
- 工夫复杂度O(logN)
var arrangeCoins = function (n) { let left = 0, right = n; while (left <= right) { const mid = left + ((right - left) >> 1); // mid 层的时候满的硬币数 const sum = ((1 + mid) * mid) / 2; if (sum === n) return mid; if (sum < n) { left = mid + 1; } else { right = mid - 1; } } return right;};33. 搜寻旋转排序数组
剖析
- 已知：原始数组 nums 是生序排序的，且数组中的值不一样的
- 入参的 nums 是在某个下标 k 的作用下产生了重置，使得 nums 当初是先升序数组 [k,len-1]而后断裂后，再一个升序数组[0,k-1]
- 这是一个部分排好序的数组，所以能够用二分解决,返回的是 target 值的下标或者 -1
- 所以每次都用排好序的一半来作为判断根据，如果在排好序这边，则删除另外，反之亦然
- 工夫复杂度 O(logn)
参考视频：传送门
var search = function (nums, target) { let left = 0, right = nums.length - 1; while (left <= right) { const mid = ((right - left) >> 1) + left; if (nums[mid] === target) return mid; if (nums[mid] >= nums[left]) { // [left,mid] 是有序的 if (nums[left] <= target && target < nums[mid]) { // target 在[left , mid) 中 right = mid - 1; } else { left = mid + 1; } } else { // [mid,right] 是有序的 if (nums[mid] < target && target <= nums[right]) { // target 在（mid , right] 中 left = mid + 1; } else { right = mid - 1; } } } return -1;};模板 2 -- 须要用到街坊值判断
相比于模板 1，模板 2 中不是仅有一个符合条件值，而是一系列值，咱们须要找到符合要求的那个 极值，比方说是符合条件的最大值/第一个值 等；
var search = function (fn) { let left = 最小值, right = 最大值; while (left <= right) { // 取 mid 值 const mid = ((right - left) >> 1) + left; //这里的 fn 可能是函数，也可能只是数组取值，反正就是能够获得一个值去跟 target 比拟 const bool = fn(mid); if (bool) { // 胜利了，要向还没胜利的中央寻找 right = mid - 1; } else { left = mid + 1; } } return 特定的值;};278. 第一个谬误的版本
剖析
- 这里要找出的是第一个谬误版本，而整顿版本排列是
失常 -> 谬误，所以这里是依据谬误向左迫近 - 如果是谬误版本， right 指针一直往左，如果是失常版本，left 指针一直往右，当左右指针相交时，如果是谬误版本，right 持续往左，达到失常区，这个时候 left 就是第一个谬误版本了
- 工夫复杂度 O(logn)
var solution = function (isBadVersion) { return function (n) { let left = 1, right = n; while (left <= right) { const mid = ((right - left) >> 1) + left; if (isBadVersion(mid)) { // 如果是谬误版本 right = mid - 1; } else { left = mid + 1; } } return left; };};162. 寻找峰值
剖析
- 已知多峰的时候只需返回一个即可，那么就是间接做二分判断即可；
- 两侧边缘值也能够是峰值,因为题目给了两侧是 -Infinity；
- 犹豫曾经存在整体区域外的最低点，所以只有找到一个部分降落区域，那么部分回升区域中必定存在峰值；
var findPeakElement = function (nums) { nums[-1] = nums[nums.length] = -Infinity; // 设置边界值，这样保障在边缘的时候也只须要两个值就能判极值 let left = 0, right = nums.length - 1; while (left <= right) { const mid = ((right - left) >> 1) + left; // 找出一个有峰值的区间 if (nums[mid] > nums[mid + 1]) { // [mid,right] 部分降落，而[-1,mid] 是部分回升的，比拟有一个最低值 right = mid - 1; } else { left = mid + 1; } } return left;};153. 寻找旋转排序数组中的最小值
剖析
- 这里其实就是找谷值，留神的是，这里的值互不相等且部分单增 ，所以能够加一个辅助条件 nums[-1] = nums[len] = infinite,这样能保障谷值在边缘也能间接找到
- 留神：这里返回的是最小值，而不是最小坐标
- 留神获得 mid 值之后，将 mid 与 right 的值比拟，只会呈现两种状况，
- 如果 nums[mid]<=nums[right] ，则 mid 和 right 重合或 mid 在 right 之后且单增，这个时候无论是在第一个单增区间还是第二个，谷点都在 mid 之钱，所以 right = mid-1
var findMin = function (nums) { let len = nums.length; nums[-1] = nums[len] = Infinity; let left = 0, right = len - 1; while (left <= right) { const mid = ((right - left) >> 1) + left; if (nums[mid - 1] > nums[mid] && nums[mid] < nums[mid + 1]) return nums[mid]; //谷值 if(nums[mid]<=nums[right]){ // [mid,right] 单增 // 留神这个等号为啥要加，能够考虑一下如果 left 和 right 相等时，对应的 mid 也是这个点，那么是让 right 走，还是让 left 走；这里咱们最初返回值是 left,所以让 right 走一步结束战斗 right = mid-1 }else{ left = mid+1 } } return nums[left];};154. 寻找旋转排序数组中的最小值 II
- 和 153. 寻找旋转排序数组中的最小值 相似，然而因为值能够反复，无奈直接判断单增区间
- 所以想方法将右侧与 mid 相等的值先删除掉，这个时候剩下的不同值能够与 153 题一样做解决了
var findMin = function(nums) { const len = nums.length nums[-1] = nums[len] = Infinity let left = 0,right = len-1 while(left<=right){ const mid = ((right-left)>>1) + left // 将右侧与 mid 同值的值删掉 while(nums[right] === nums[mid] && right>mid){ right -- } // 因为存在反复值，所以拐点值右侧能够是直线，而不肯定是单增 if(nums[mid-1]>nums[mid] && nums[mid]<=nums[mid+1]) return nums[mid] if(nums[mid]<=nums[right]){ // 上一题这里的等号是当 left 和 right 重合时的非凡状况 // 当初因为值可能反复，所以不能直接判断出 [mid,right] 是递增的区间了，所以要先为右侧雷同的值进行删减，而后再进行即可 right = mid-1 }else{ left = mid+1 } } return nums[left]};模板3
在排序数组中查找元素的第一个和最初一个地位
剖析
- 失常查找 target 值，直到找到左侧第一个，
- 如果没有找到，则间接返回 [-1,-1]
- 如果找到了左侧的 target 值，这个时候以左侧 left 为终点，再进行一次二分，求右侧第一个 target 值，最初返回即可
- 工夫复杂度 O(logn)
var searchRange = function(nums, target) { if(!nums) return [-1,-1] let left = 0,right = nums.length-1 let ret = [] // 找左节点 while(left<=right){ const mid = ((right-left)>>1) + left if(nums[mid]<target){ left = mid+1 }else{ right = mid-1 } } if(nums[left]!== target) return [-1,-1] // 找右节点 let l = left,r = nums.length-1 while(l<=r){ const mid = ((r-l)>>1) + l if(nums[mid]>target){ r = mid-1 }else{ l = mid+1 } } return [left,r]};658. 找到 K 个最靠近的元素
剖析
- 先找出 arr 中值最靠近 x 左侧的下标值 -- 如果有等于 x 的就取 x 没有就取最靠近的前一个
- 而后开始向两边扩散找靠近 x 的前 k 个值
- 工夫复杂度 O(log(n))
var findClosestElements = function (arr, k, x) { let l = 0, r = arr.length - 1; while (l <= r) { const mid = ((r - l) >> 1) + l; if (arr[mid] > x) { r = mid - 1; } else { l = mid + 1; } } // 这个时候 r 是左侧最靠近 x 的值下标，l 是右侧最靠近 x 的值 let lIndex = r, rIndex = l; // 避免混同 let ret = []; while (k--) { let isLeft = true; if (lIndex >= 0 && rIndex < arr.length) { isLeft = x - arr[lIndex] <= arr[rIndex] - x; } else if (rIndex < arr.length) { isLeft = false; } if (isLeft) { ret.unshift(arr[lIndex]); lIndex--; } else { ret.push(arr[rIndex]); rIndex++; } } return ret;};其余练习题
50. Pow(x, n)
剖析
- 间接将 n 进行拆分，而后递归求值 -- 而后超时了，因为很多值都是反复的，
- 而后就是疾速迭代咱们 2 - 4 -16
- 值得注意的是，这里 n 的取值是 [-2^31,2^31-1] 原本没啥事，然而吧，你将 n 转成负数再执行, 那么 n >> 1 就有事了，一旦 n 是 -2^31,那么第一次递归的时候 recursion 的 n 就是正数了
- 所以要用 >>> 或者用数学的办法
- 工夫复杂度 O(logn)
var myPow = function (x, n) { const recursion = (n) => { if (n === 0) return 1; // const y = recursion(n >> 1); const y = recursion(Math.floor(n / 2)); return n % 2 ? y * y * x : y * y; }; return n < 0 ? 1 / recursion(-n) : recursion(n);};console.log(myPow(2.1, 3));console.log(myPow(2, -2));367. 无效的齐全平方数
/** * @剖析 * 1. 概念：若 x*x = y ， 则 y 是齐全平方数 */var isPerfectSquare = function (num) { let left = 0, right = num; while (left <= right) { const mid = ((right - left) >> 1) + left; const temp = mid * mid; if (temp === num) return true; if (temp > num) { right = mid - 1; } else { left = mid + 1; } } return false;};744. 寻找比指标字母大的最小字母
剖析:
- 留神： 这道题应该改成，给定一个排好序的字符数组，找出处 target 所在位置的下一个字母，且该数组首尾连接 -- 即如果给定的 target 在数组最初，则下一个就是首字母；
- 字母先转成 UniCode 编码，而后用 编码大小来进行比拟，留神这里只有小写字母，所以 left right 值也是有了
- 这是个奇葩的设定，['a','c'],'z' , 如果依照真正 charCode 比拟，数组中没有比 'z' 大的，这里这能说是程序遍历数组后，在 target 之后的第一个元素
- 工夫复杂度: O(logN)
var nextGreatestLetter = function(letters, target) { const targetIndex = target.charCodeAt() let left = 0,right = numbers.length-1 while(left <= right){ const mid = ((right-left) >> 1) + left if(letters[mid].charCodeAt()>targetIndex){ // 只有是合乎的，都返回往左走，晓得走不了 right = mid-1 }else{ left= mid+1 } } if(left>=numbers.length) return letters[0] return letters[left]};349. 两个数组的交加
剖析：
- 先为 nums1 和 nums2 排序，而后遍历其中一个数组，另外一个数组做二分查找，最初失去后果
- 这里间接取nums1 做遍历，理论能够找个长度少的遍历，长度大的做二分，这样查找过程的工夫复杂度即为 O(nlogm), 其中 n<=m
- 然而因为做了排序，理论的工夫复杂度是 mlogm m 是大的那个长度
var intersection = function (nums1, nums2) { const l1 = nums1.length, l2 = nums2.length; if (!l1 || !l2) return []; // 先排序 nums1.sort((a, b) => a - b); nums2.sort((a, b) => a - b); const ret = []; for (let i = 0;i<l1;i++) { if(i>0 && nums1[i-1] === nums1[i]) continue // 反复值跳过 const n = nums1[i]; let left = 0, right = l2-1; while (left <= right) { const mid = ((right - left) >> 1) + left; if (nums2[mid] === n) { ret.push(n); break; } if (nums2[mid] > n) { right = mid - 1; } else { left = mid + 1; } } } return ret};350. 两个数组的交加 II
- 间接用 map 将其中一个数组的值映射保存起来
- 而后遍历另外的数组，每一次匹配胜利，则map 的值减一，ret 数组 push 上这个值
- 直到 map 中的这个值为 0，则这个值在两个数组中的最大公约数达到，不再进行 push 咯
- 工夫复杂度 O(n+m) , 空间复杂度 O(n) 其中 n 能够是小的那个数组的不同值长度
var intersect = function (nums1, nums2) { const map = new Map(); //将长数组的值存储一份 for (let item of nums2) { if (map.has(item)) { map.set(item, map.get(item) + 1); } else { map.set(item, 1); } } let ret = []; for(let item of nums1){ if(!!map.get(item)){ map.set(item,map.get(item)-1) ret.push(item) } } return ret;};167. 两数之和 II - 输出有序数组
剖析
- numbers 是升序数组，找出 n1+n2 = target , 返回 n1,n2 对应的下标值 [i1,i2] -- 留神下标值从 1 开始
- 每个输出只有惟一的输入值
- 工夫复杂度 nlogn
var twoSum = function (numbers, target) { for (let i = 0; i < numbers.length-1; i++) { const temp = target - numbers[i]; let l = i + 1, r = numbers.length - 1; while (l <= r) { const mid = ((r - l) >> 1) + l; if (numbers[mid] === temp) return [i + 1, mid + 1]; if (numbers[mid] < temp) { left = mid + 1; } else { right = mid - 1; } } }};287. 寻找反复数
剖析
- 给定长度为 n+1 的 nums，外面的值都是 1-n, 本题中只有一个值是反复的，找出这个值
- 留神这里只是表明反复的只有一个值，然而这个值反复多少次并没有阐明，所以不能用简略的异或二进制解决
- 然而咱们能够选定以 mid 值，而后判断小于等于 mid 值 count，如果 count 超出了 mid ，证实在 [1,mid] 中至多有一个值反复了，这个时候能够砍掉右侧局部
- 当 left 和 right 相等之后，即找到了惟一反复的值，因为这个时候左右两侧的值都不服要求，就只有这个了
- 工夫复杂度 O(nlohn), 空间复杂度 1
var findDuplicate = function (nums) { let left = 1, right = nums.length - 1; // 值是 1 - n while (left < right) { const mid = ((right - left) >> 1) + left; const count = nums.reduce((prev, cur) => (cur <= mid ? prev + 1 : prev), 0); // 小于等于 count 的值 if (count > mid) { // 如果 [1,mid] 这个数组满值的状况才只有 mid 个，当初 count 如果比这个还大，证实反复的值在这外面 right = mid; } else { left = mid + 1; } } return left;};4.寻找两个正序数组的中位数
剖析
- 已知两个有序数据，求中位数 （和求第 k 小没啥区别）
- 依据两个数组的大小，将题转成求第 k 小的题目
- 这题应用二分没能间接过，断定条件边界很多，最初放弃间接用二分解决掉了
var findMedianSortedArrays = function (nums1, nums2) { const n = nums1.length, m = nums2.length; let sum = n + m; // 如果是偶数，取两个值 prev,cur ,取两头值 let k = (sum + 1) / 2; // 能够是非整数 let cur; while (k >= 1) { if (!nums1.length) { cur = nums2.shift(); } else if (!nums2.length) { cur = nums1.shift(); } else { if (nums1[0] <= nums2[0]) { cur = nums1.shift(); } else { cur = nums2.shift(); } } k--; } let next; if (k !== 0) { // 这里用 ?? 而不是用 || , 是因为判断 nums[0] 是否为 undefined，而如果是 0 的时候，取 0 而非切换到 Infinity; next = Math.min(nums1[0] ?? Infinity, nums2[0] ?? Infinity); return (cur + next) / 2; } return cur;};410. 宰割数组的最大值
剖析
- 切分数组 nums，使得切割后数组和最大的那个值最小 -- 子数组是间断的；
- 也就是尽可能依照总和平均的将值调配到每一个数组中，且每个数组中起码有一个值,所以最小值应该就是 max(nums[i]), 最大值是 sum(nums)
- 设计一个函数 check(max), 判断是否能切割出 m 个间断子数组，且值小于等于 max；如果能够，证实这个是一个较大值，能够持续向左侧迫近，找到一个更小的值；如果不能够，证实这个值 max 偏小了，需要求的值在右侧.
- 这里最须要留神的是，切割的子组件是间断的；同时每一个数组至多有一个值；
- 只有捋分明 check 这个函数，根本就能每次都切掉一半，间接拿到最初值了；
var splitArray = function (nums, m) { // 先找到 left 和 right let left = 0, right = 0; for (let num of nums) { left = Math.max(num, left); right += num; } // 切割最大值不超过 max 的数组，如果切出来的数组数量少于 m，则证实能够切得更新，施展 true // 如果切除来的数组数量超出了 m, 证实只且 m 组的时候，最小值要超出 max 了，返回 false function check(max) { let ret = 0, sum = 0; let i = 0; while (i < nums.length) { sum += nums[i]; if (sum >max) { // 一旦超出 max，则分组完结，sum 从新设置为 nums[i] ret++; sum = nums[i]; } i++ } // 如果最初还有剩，独自成团 ret = sum ? ret + 1 : ret; return ret<=m } while (left <= right) { const mid = ((right - left) >> 1) + left; if (check(mid)) { // 如果能找到，向左迫近 -- right 最初失去的是一个不胜利的值，因为只有胜利它就要产生扭转 right = mid - 1; } else { // left 最终进来的时候，必定代表一个胜利的值 left = mid + 1; } } return left; };