Hallo，我们好。在作业的过程中，发现算法越来越重要‼️于是笔者决定从头系统性地学习算法。同时，开设了个算法专栏，打算记载这个学习的过程。但因为或许时刻或个人原因(懒)，更新的时刻或许就会很随缘……

「二分查找」的思维在日子和作业中很常见，经过不断缩小查找区间的规模(减治思维)，直到找到方针元素或许没有找到方针元素。

减治思维

减是「削减问题规划」，治是「处理」。浅显来说，便是「扫除法」，即：每一轮扫除去必定「不存在方针元素」的区间，在剩余「或许存在方针元素」的区间里持续查找。使得问题的规划逐步削减。因为问题的规划是有限的，经过有限次的操作，问题就得以处理。

例子：
「猜价格」游戏。游戏规则是：给出一个产品，告知学生它的价格在多少元（价格为整数）以内，让学生猜，假如猜出的价格低于真实价格，教师就说少了，高于真实的价格，就说多了，看谁能在最短的时刻内猜中。

假定产品为37元。

‍教师：在1～100元之间。

‍学生：50元。

‍教师：多了。

‍学生：25元。

‍教师：少了。

‍学生：37元。

‍教师：正确。

这个游戏便是运用「减治思维」完结「猜价格」使命的。教师说「多了」或许「少了」，便是给学生反应，让学生逐步缩小价格区间，终究猜中价格。

运用规模

二分下标

在有序数组中进行查找一个数

数组和有序是要害。

数组具有「随机拜访」的特性，因为数组在内存中接连存放，因而能够经过数组的下标快速地拜访到这个元素。

「有序」不必定要求方针元素地点的区间是有序数组，也便是说「有序」这个条件能够放宽，「半有序」数组或许「山脉」数组里都能够运用二分查找算法。

二分答案

在整数规模内查找一个整数

假如要找的是一个整数，而且知道这个整数的规模，就能够运用二分查找算法，逐步缩小整数的规模。

假定要找的数最小值为0，最大值为N，就能够把这个整数幻想成数组 [0, 1, 2,..., N] 里的一个值，这个数组的「下标」和「值」是相同的，找数组的下标就等于找数组的值。

处理思路

运用「减治思维」，一般有两种处理思路，但仅是细节上的不同。

以最基本的 leetcode 704.二分查找为例：

/**
 * leetcode 704.二分查找 - 简略
 *
 * @remarks
 * 给定一个`n`个元素有序的（升序）整型数组`nums`和一个方针值`target`，
 * 写一个函数查找`nums`中的`target`，假如方针值存在回来下标，不然回来`-1`。
 *
 * @example
 * nums = [-1,0,3,5,9,12], target = 9
 * 输出：4
 */

循环体中查找元素

分析：处理这个问题的思路和「猜价格」游戏是相同的。因为数组是有序且升序的数组，二分查找的思路是，先看数组的「中心元素」：

假如「中心」元素等于「方针」元素，就直接回来该元素下标；
不然就需求在「中心」元素的左边或许右边持续查找。

var search = function(nums, target) {
    const len = nums.length;
    let [left, right] = [0, len - 1]
    while(left <= right) {
        let mid = parseInt(left + (right - left) / 2);
        if (nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1
        } else {
            return mid
        }
    }
    return -1
}

每一次都会在一个区间里查找方针元素。所以需求两个变量表明数组里区间的「左右鸿沟」，分别用变量left和right表明，左鸿沟的值等于 0，右鸿沟的值等于数组的长度减1；
接下来是循环体，循环持续的条件是left <= right，表明：在区间只有1个元素的时分，仍需进行逻辑判别。这个逻辑是，查看区间里坐落中心的那个元素的值：
- 假如它是「方针」元素，则回来其下标；
- 假如「中心」元素比「方针」元素「严厉小」。「中心方位」以及「中心方位的左边」的一切元素的数值必定比方针元素「小」，那么下一轮查找区间为[left = mid + 1, right]；
- 假如「中心」元素比「方针」元素「严厉大」，「中心方位」以及「中心方位的右边」的一切元素的数值必定比方针元素「大」，那么下一轮查找区间为 [left, right = mid - 1]；
退出循环后，表明不存在方针元素，回来−1；

循环体中扫除区间

日子中咱们往往很清楚自己「不需求什么」，但是不清楚自己「需求什么」。所以，从「中心元素」在什么情况下「不是方针元素」考虑，会使得问题变得简略。

分析：标题要找== target的元素。对这个性质取反，便是!= target，也便是< target或许> target，这两个条件选择其间一个，都能够缩小问题的区间。

< target：

var search = function(nums, target) {
    const len = nums.length
    let [left, right] = [0, len - 1]
    let midIndex
    while (right > left) {
        midIndex = Math.floor(left + (right - left) / 2)
        if (nums[midIndex] < target) {
            left = midIndex + 1
        } else {
            right = midIndex
        }
    }
    if (nums[left] === target) {
        return left
    }
    return -1
};

> target：

var search = function(nums, target) {
    const len = nums.length
    let [left, right] = [0, len - 1]
    let midIndex
    while (right > left) {
        midIndex = Math.ceil(left + (right - left) / 2)
        if (nums[midIndex] > target) {
            right = midIndex - 1
        } else {
            left = midIndex
        }
    }
    if (nums[left] === target) {
        return left
    }
    return -1
};

循环能够持续的条件是left < right。在「循环体中查找元素」中，当left == right，「左右鸿沟」重合的时分，区间里只有一个元素时，查找持续；而在「循环体中扫除区间」，在left == right时退出了循环，表明区间里只剩余一个元素时，退出循环；
在退出循环今后，还需求独自做一次判别(若要找的「方针元素必定落在给的区间内」，那么该判别能够省略)；

实现细节

二分查找算法在实现的过程中，很简略呈现「鸿沟」问题、「中心值」问题等，因而需求留意细节的实现。

循环持续条件

循环体中查找元素：while (left <= right);
循环体中扫除区间：while (left < right);

取中心值法

取中心数的代码(left + right) / 2，在left和right很大时，left + right有或许会发生整型溢出(2^53)。因而能够改用以下写法，left + (right - left) / 2或许(left + right) >> 1。

>>表明「位运算」中的「右移」，整型「右移」一位相当于/2。但高档编程言语在/2时，底层都会转化成为「位运算」。为了代码的易读性，不建议这样写。

中心值上下取整

向下取整：Math.floor(left + (right - left) / 2);
- 运用「循环体中扫除区间」思路，且区间剩余两个元素时，采纳「向下取整」，此刻left == mid，若后续代码呈现left = mid，或许会堕入「死循环」。
向上取整：Math.ceil(left + (right - left) / 2);
- 运用「循环体中扫除区间」思路，且区间剩余两个元素时，采纳「向下取整」，此刻right == mid，若后续代码呈现right = mid，或许会堕入「死循环」。

因而，在决定「向上/下取整」时，需求依据后续的逻辑而改动。

小技巧：呈现left = mid时，中心值「向上取整」；呈现right = mid时，中心值「向下取整」。

lc例题

⚠️：以下代码并不是「官方题解」或「最优解」，仅仅是笔者根据「二分查找」思路的实现。

二分下标

指在一个有序数组（该条件能够适当放宽）中查找方针元素的下标。

35 – 简略

查找刺进方位

/**
 * leetcode 35.查找刺进方位 - 简略
 *
 * @remarks
 * 给定一个排序数组和一个方针值，在数组中找到方针值，并回来其索引。
 * 假如方针值不存在于数组中，回来它将会被按顺序刺进的方位。
 *
 * @example
 * 输入: nums = [1,3,5,6], target = 5
 * 输出: 2
 */
const search_35 = (nums, target) => {
	const len = nums.length;
	if (!len) return 0;
	let [left, right] = [0, len];
	while (left < right) {
		let mid = Math.floor(left + (right - left) / 2);
		if (target > nums[mid]) {
			left = mid + 1;
		} else {
			right = mid;
		}
	}
	return left;
};

34 – 中等

在排序数组中查找元素的第一个和最终一个方位

/**
 * leetcode 34.在排序数组中查找元素的第一个和最终一个方位 - 中等
 *
 * @remarks
 * 给你一个依照非递减顺序摆放的整数数组 nums，和一个方针值 target。
 * 请你找出给定方针值在数组中的开端方位和结束方位。
 * 假如数组中不存在方针值 target，回来 [-1, -1]。
 *
 * @example
 * 输入：nums = [5,7,7,8,8,10], target = 8
 * 输出：[3,4]
 *
 * @example
 * 输入：nums = [5,7,7,8,8,10], target = 6
 * 输出：[-1,-1]
 */
const search_34 = (nums, target) => {
	const len = nums.length;
	if (!len) return [-1, -1];
	let [left, right] = [0, len - 1];
	let [round_left, round_right] = [0, len - 1];
	while (left < right) {
		let mid = Math.floor(left + (right - left) / 2);
		if (target > nums[mid]) {
			left = mid + 1;
		} else {
			right = mid;
		}
	}
	if (nums[left] !== target) return [-1, -1];
	while (round_left < round_right) {
		let mid = Math.ceil(round_left + (round_right - round_left) / 2);
		if (target < nums[mid]) {
			round_right = mid - 1;
		} else {
			round_left = mid;
		}
	}
	return [left, round_left];
};

153 – 中等

寻觅旋转排序数组中的最小值

/**
 * leetcode 153.寻觅旋转排序数组中的最小值 - 中等
 *
 * @remarks
 * 已知一个长度为 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 ，它原来是一个升序摆放的数组，并按上述景象进行了屡次旋转。请你找出并回来数组中的 最小元素 。
 *
 * @example
 * 输入：nums = [3,4,5,1,2]
 * 输出：1
 */
const search_153 = (nums) => {
	const len = nums.length;
	let [left, right] = [0, len - 1];
	while (left < right) {
		let mid = Math.floor(left + (right - left) / 2);
		if (nums[left] < nums[right]) return nums[left];
		if (nums[mid] > nums[right]) {
			left = mid + 1;
		} else {
			right = mid;
		}
	}
	return nums[left];
};

154 – 困难

寻觅旋转排序数组中的最小值 II

/**
 * leetcode 154.寻觅旋转排序数组中的最小值 II - 困难
 *
 * @remarks
 * 已知一个长度为 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 ，它原来是一个升序摆放的数组，并按上述景象进行了屡次旋转。请你找出并回来数组中的 最小元素 。
 * 
 * @example
 * 输入：nums = [1,3,5]
 * 输出：1
 */
const search_154 = (nums) => {
	const len = nums.length;
	let [left, right] = [0, len - 1];
	while (left < right) {
		let mid = Math.floor(left + (right - left) / 2);
		if (nums[left] < nums[right]) return nums[left];
		if (nums[left] === nums[right]) {
			right -= 1;
		} else if (nums[mid] > nums[right]) {
			left = mid + 1;
		} else {
			right = mid;
		}
	}
	return nums[left];
};

33 – 中等

查找旋转排序数组

/**
 * leetcode 33.查找旋转排序数组 - 中等
 *
 * @remarks
 * 整数数组 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 。
 *
 * @examle
 * 输入：nums = [4,5,6,7,0,1,2], target = 0
 * 输出：4
 */
const search_33 = (nums, target) => {
	const len = nums.length;
	let [left, right] = [0, len - 1];
	while (left + 1 < right) {
		let mid = Math.floor(left + (right - left) / 2);
		// 未经旋转
		if (nums[right] > nums[left]) {
			if (target > nums[mid]) {
				left = mid + 1;
			} else {
				right = mid;
			}
			continue;
		}
		// 前半区有序
		if (nums[mid] > nums[left]) {
			// 方针在此前半区
			if (nums[left] <= target && nums[mid] >= target) {
				right = mid;
			} else {
				left = mid;
			}
		}
		// 后半区有序
		if (nums[right] > nums[mid]) {
			// 方针在后区域
			if (nums[mid] <= target && nums[right] >= target) {
				left = mid;
			} else {
				right = mid;
			}
		}
	}
	if (nums[left] === target) return left;
	if (nums[right] === target) return right;
	return -1;
};

81 – 中等

查找旋转排序数组 II

/**
 * leetcode 81.查找旋转排序数组 II - 中等
 *
 * @remarks
 * 已知存在一个按非降序摆放的整数数组 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,4,4,5,6,6,7] 在下标 5 处经旋转后或许变为 [4,5,6,6,7,0,1,2,4,4] 。
 * 给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判别给定的方针值是否存在于数组中。假如 nums 中存在这个方针值 target ，则回来 true ，不然回来 false 。
 *
 * @expamle
 * 输入：nums = [2,5,6,0,0,1,2], target = 0
 * 输出：true
 *
 * @example
 * 输入：nums = [2,5,6,0,0,1,2], target = 3
 * 输出：false
 */
const search_81 = (nums, target) => {
	const len = nums.length;
	let [left, right] = [0, len - 1];
	while (left + 1 < right) {
		let mid = Math.floor(left + (right - left) / 2);
		if (nums[right] === nums[left]) {
			right -= 1;
			continue;
		}
		// 有序
		if (nums[right] > nums[left]) {
			if (target > nums[mid]) {
				left = mid + 1;
			} else {
				right = mid;
			}
			continue;
		}
		// 前半区有序
		if (nums[mid] >= nums[left]) {
			// 方针在此前半区
			if (nums[left] <= target && nums[mid] >= target) {
				right = mid;
			} else {
				left = mid;
			}
		}
		// 后半区有序
		if (nums[right] >= nums[mid]) {
			// 方针在后区域
			if (nums[mid] <= target && nums[right] >= target) {
				left = mid;
			} else {
				right = mid;
			}
		}
	}
	return nums[left] === target || nums[right] === target;
};

278 – 简略

第一个过错的版别

/**
 * leetcode 278.第一个过错的版别 - 简略
 *
 * @remarks
 * 你是产品司理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版别没有经过质量检测。
 * 因为每个版别都是根据之前的版别开发的，所以过错的版别之后的一切版别都是错的。
 * 假定你有 n 个版别 [1, 2, ..., n]，你想找出导致之后一切版别犯错的第一个过错的版别。
 * 你能够经过调用 bool isBadVersion(version) 接口来判别版别号 version 是否在单元测试中犯错。
 * 实现一个函数来查找第一个过错的版别。你应该尽量削减对调用 API 的次数。
 * 
 * @example
 * 输入：n = 5, bad = 4
 * 输出：4
 */
const search_278 = (n) => {
	let [left, right] = [0, n];
	while (left < right) {
		let mid = Math.floor(left + (right - left) / 2);
		if (isBadVersion(mid)) {
			right = mid;
		} else {
			left = mid + 1;
		}
	}
	return left;
};

852 – 中等

山脉数组的峰顶索引

/**
 * leetcode 852.山脉数组的峰顶索引 - 中等
 *
 * @remarks
 * 符合下列属性的数组 arr 称为 山脉数组 ：
 * arr.length >= 3
 * 存在 i（0 < i < arr.length - 1）使得：
 * arr[0] < arr[1] < ... arr[i-1] < arr[i]
 * arr[i] > arr[i+1] > ... > arr[arr.length - 1]
 * 给你由整数组成的山脉数组 arr ，回来任何满意 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i 。
 *
 * @example
 * 输入：arr = [0,10,5,2]
 * 输出：1
 *
 * @example
 * 输入：arr = [3,4,5,1]
 * 输出：2
 *
 * @example
 * 输入：arr = [24,69,100,99,79,78,67,36,26,19]
 * 输出：2
 */
const search_852 = (arr) => {
	const len = arr.length;
	let [left, right] = [0, len - 1];
	while (left < right) {
		let mid = Math.floor(left + (right - left) / 2);
		// 左山峰
		if (arr[mid] < arr[mid + 1]) {
			left = mid + 1;
			// 右山峰
		} else {
			right = mid;
		}
	}
	return left;
};

1095 – 困难

山脉数组中查找方针值

/**
 * leetcode 1095.山脉数组中查找方针值 - 困难
 *
 * @remarks
 * 给你一个 山脉数组 mountainArr，请你回来能够使得 mountainArr.get(index) 等于 target 最小 的下标 index 值。
 * 假如不存在这样的下标 index，就请回来 -1。
 * 你将 不能直接拜访该山脉数组，有必要经过 MountainArray 接口来获取数据：
 * MountainArray.get(k) - 会回来数组中索引为k 的元素（下标从 0 开端）
 * MountainArray.length() - 会回来该数组的长度
 *
 * @example
 * 输入：array = [1,2,3,4,5,3,1], target = 3
 * 输出：2
 * 解释：3 在数组中呈现了两次，下标分别为 2 和 5，咱们回来最小的下标 2。
 *
 * @example
 * 输入：array = [0,1,2,4,2,1], target = 3
 * 输出：-1
 * 解释：3 在数组中没有呈现，回来 -1。
 */
const search_1095 = (target, mountainArr) => {
	const len = mountainArr.length();
	let [left, right] = [0, len - 1];
	let top = 0;
	// 寻觅最高峰
	while (left + 1 < right) {
		let mid = Math.floor(left + (right - left) / 2);
		// 左山峰
		if (mountainArr.get(mid) < mountainArr.get(mid + 1)) {
			left = mid + 1;
			// 右山峰
		} else {
			right = mid;
		}
	}
	top = mountainArr.get(left) > mountainArr.get(right) ? left : right;
	// 左山峰查找
	left = 0;
	right = top;
	while (left < right) {
		let mid = Math.floor(left + (right - left) / 2);
		if (mountainArr.get(mid) < target) {
			left = mid + 1;
		} else {
			right = mid;
		}
	}
	if (target === mountainArr.get(left)) return left;
	// 右山峰查找
	left = top + 1;
	right = len - 1;
	while (left < right) {
		let mid = Math.ceil(left + (right - left) / 2);
		if (mountainArr.get(mid) < target) {
			right = mid - 1;
		} else {
			left = mid;
		}
	}
	if (target === mountainArr.get(left)) return left;
	return -1;
};

4 – 困难

寻觅两个正序数组的中位数

/**
 * leetcode 4.寻觅两个正序数组的中位数 - 困难
 *
 * @remarks
 * 给定两个巨细分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并回来这两个正序数组的 中位数 。
 * 算法的时刻复杂度应该为 O(log (m+n))
 *
 * @example
 * 输入：nums1 = [1,3], nums2 = [2]
 * 输出：2.00000
 */
const search_4 = (nums1, nums2) => {
	// 确保上数组的长度要小于下数组
	if (nums1.length > nums2.length) {
		[nums1, nums2] = [nums2, nums1];
	}
	const nums1_len = nums1.length;
	const nums2_len = nums2.length;
	// 左半区元素个数（确保左半区元素个数等于右半区元素个数或许只多一个）
	// 关于数组长度和为偶数时，因为采纳向下取整，所以能够 + 1
	// 关于数组长度和为奇数时，左半区比右半区多一个，所以能够 + 1
	// 因而一致 + 1 处理
	let total_left = Math.floor((nums1_len + nums2_len + 1) / 2);
	// 在 nums1 的 [0, nums1_len]区间寻觅切割线
	// 该切割线满意 nums1[i - 1] <= nums2[j] && nums1[i] >= nums2[j - 1]
	let [left, right] = [0, nums1_len];
	while (left < right) {
		let i = Math.ceil(left + (right - left) / 2);
		let j = total_left - i;
		if (nums1[i - 1] > nums2[j]) {
			right = i - 1;
		} else {
			left = i;
		}
	}
	// 确认切割线方位
	let [i, j] = [left, total_left - left];
	const nums1_left = i === 0 ? -1 * Number.MAX_VALUE : nums1[i - 1];
	const nums1_right = i === nums1_len ? Number.MAX_VALUE : nums1[i];
	const nums2_left = j === 0 ? -1 * Number.MAX_VALUE : nums2[j - 1];
	const nums2_right = j === nums2_len ? Number.MAX_VALUE : nums2[j];
	// 偶数
	if ((nums1_len + nums2_len) % 2 === 0) {
		return (
			((nums1_left > nums2_left ? nums1_left : nums2_left) +
				(nums1_right < nums2_right ? nums1_right : nums2_right)) /
			2
		);
		// 奇数
	} else {
		return nums1_left > nums2_left ? nums1_left : nums2_left;
	}
};

二分答案

要求找的是一个整数，而且知道这个整数「最小值」和「最大值」。此刻，能够考虑运用二分查找算法找到这个方针值。

69 – 简略

x 的平方根

/**
 * leetcode 69.x 的平方根 - 简略
 *
 * @remarks
 * 给你一个非负整数 x ，计算并回来 x 的 算术平方根 。
 * 因为回来类型是整数，成果只保存 整数部分 ，小数部分将被 舍去 。
 *
 * @example
 * 输入：x = 4
 * 输出：2
 */
const search_69 = (x) => {
	if (x === 1) return 1;
	let [left, right] = [0, x];
	while (left + 1 < right) {
		let mid = Math.floor(left + (right - left) / 2);
		let result = mid * mid;
		if (result > x) {
			right = mid;
		} else {
			left = mid;
		}
	}
	return left;
};

287 – 中等

寻觅重复数

/**
 * leetcode 287.寻觅重复数 - 中等
 *
 * @remarks
 * 给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 规模内（包含 1 和 n），可知至少存在一个重复的整数。
 * 假定 nums 只有 一个重复的整数 ，回来 这个重复的数 。
 * 你规划的处理方案有必要 不修改 数组 nums 且只用常量级 O(1) 的额定空间。
 *
 * @example
 * 输入：nums = [1,3,4,2,2]
 * 输出：2
 */
const search_287 = (nums) => {
	const len = nums.length;
	if (len === 2) return nums[0];
	let [left, right, answer] = [1, len - 1, -1];
	while (right >= left) {
		let [mid, count] = [Math.floor(left + (right - left) / 2), 0];
		for (let i = 0; i < len; i++) {
			if (nums[i] <= mid) {
				count++;
			}
		}
		if (count <= mid) {
			left = mid + 1;
		} else {
			right = mid - 1;
			answer = mid;
		}
	}
	return answer;
};

1300 – 中等

改变数组后最接近方针值的数组和

/**
 * leetcode 1300.改变数组后最接近方针值的数组和 - 中等
 *
 * @remarks
 * 给你一个整数数组 arr 和一个方针值 target ，请你回来一个整数 value ，
 * 使得将数组中一切大于 value 的值变成 value 后，数组的和最接近  target （最接近表明两者之差的绝对值最小）。
 * 假如有多种使得和最接近 target 的方案，请你回来这些整数中的最小值。
 * 请留意，答案不必定是 arr 中的数字。
 *
 * @example
 * 输入：arr = [4,9,3], target = 10
 * 输出：3
 */
const search_1300 = (arr, target) => {
	const len = arr.length;
	arr.sort();
	let [left, right] = [0, arr[len - 1]];
	while (left < right) {
		let mid = Math.ceil(left + (right - left) / 2);
		const total = arr.reduce((total, num) => {
			total += num >= mid ? mid : num;
			return total;
		}, 0);
		if (total > target) {
			right = mid - 1;
		} else {
			left = mid;
		}
	}
	const total_left = arr.reduce((total, num) => {
		total += num > left ? left : num;
		return total;
	}, 0);
	const total_right = arr.reduce((total, num) => {
		total += num > left + 1 ? left + 1 : num;
		return total;
	}, 0);
	return Math.abs(total_left - target) > Math.abs(total_right - target)
		? left + 1
		: left;
};

复杂的判别条件

「方针变量」和「另一个变量」有相关关系（一般来说是线性关系），方针变量的性质欠好推测，但是另一个变量的性质相对简略推测。这样的问题的判别函数通常会写成一个「函数」的形式。

875 – 中等

爱吃香蕉的珂珂

/**
 * leetcode 875.爱吃香蕉的珂珂 - 中等
 *
 * @remarks
 * 珂珂喜爱吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。保镳现已离开了，将在 h 小时后回来。
 * 珂珂能够决定她吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。假如这堆香蕉少于 k 根，她将吃掉这堆的一切香蕉，然后这一小时内不会再吃更多的香蕉。
 * 珂珂喜爱慢慢吃，但仍然想在保镳回来前吃掉一切的香蕉。
 * 回来她能够在 h 小时内吃掉一切香蕉的最小速度 k（k 为整数）。
 *
 * @example
 * 输入：piles = [3,6,7,11], h = 8
 * 输出：4
 *
 * @example
 * 输入：piles = [30,11,23,4,20], h = 5
 * 输出：30
 *
 */
const search_875 = (piles, h) => {
	const len = piles.length;
	let [left, right, mid, hour] = [0, Math.max(...piles), 0, 0];
	while (left < right) {
		mid = Math.floor(left + (right - left) / 2);
		hour = h;
		for (let i = 0; i < len; i++) {
			if (hour >= 0) {
				hour -= Math.ceil(piles[i] / mid);
			} else {
				break;
			}
		}
		if (hour >= 0) {
			right = mid;
		} else {
			left = mid + 1;
		}
	}
	return left;
};

410 – 困难

切割数组的最大值

/**
 * leetcode 410.切割数组的最大值 - 困难(贪心 + 二分)
 *
 * @remarks
 * 给定一个非负整数数组 nums 和一个整数 m ，你需求将这个数组分红 m 个非空的接连子数组。
 * 规划一个算法使得这 m 个子数组各自和的最大值最小。
 *
 * @example
 * 输入：nums = [7,2,5,10,8], m = 2
 * 输出：18
 */
const search_410 = (nums, k) => {
	let [min, max] = [Math.max(...nums), eval(nums.join("+"))];
	while (min < max) {
		let mid = Math.floor(min + (max - min) / 2);
		if (check_410(nums, mid, k)) {
			max = mid;
		} else {
			min = mid + 1;
		}
	}
	return min;
};
const check_410 = (nums, mid, k) => {
	let count = 1;
	let sum = 0;
	for (let i = 0; i < nums.length; i++) {
		if (sum + nums[i] > mid) {
			count++;
			sum = nums[i];
		} else {
			sum += nums[i];
		}
	}
	return count <= k;
};

1011 – 中等

在 D 天内送达包裹的才能

/**
 * leetcode 1011.在 D 天内送达包裹的才能 - 中等
 *
 * @remarks
 * 传送带上的包裹有必要在 days 天内从一个港口运送到另一个港口。
 * 传送带上的第 i 个包裹的分量为 weights[i]。每一天，咱们都会按给出分量（weights）的顺序往传送带上装载包裹。
 * 咱们装载的分量不会超越船的最大运载分量。
 * 回来能在 days 天内将传送带上的一切包裹送达的船的最低运载才能。
 *
 * @example
 * 输入：weights = [3,2,2,4,1,4], days = 3
 * 输出：6
 */
const search_1011 = (weights, days) => {
	let [left, right] = [Math.max(...weights), eval(weights.join("+"))];
	while (left < right) {
		let mid = Math.floor(left + (right - left) / 2);
		// 以mid的运力送完，时刻是否不超越days
		if (check_1011(weights, mid, days)) {
			right = mid;
		} else {
			left = mid + 1;
		}
	}
	return left;
};
const check_1011 = (weights, mid, days) => {
	let count = 1;
	let sum = 0;
	for (let i = 0; i < weights.length; i++) {
		if (sum + weights[i] > mid) {
			count++;
			sum = weights[i];
		} else {
			sum += weights[i];
		}
	}
	return count <= days;
};

1482 – 中等

制造 m 束花所需的最少天数

/**
 * leetcode 1482.制造 m 束花所需的最少天数 - 中等
 *
 * @remarks
 * 给你一个整数数组 bloomDay，以及两个整数 m 和 k 。
 * 现需求制造 m 束花。制造花束时，需求运用花园中 相邻的 k 朵花 。
 * 花园中有 n 朵花，第 i 朵花会在 bloomDay[i] 时怒放，刚好 能够用于 一束 花中。
 * 请你回来从花园中摘 m 束花需求等候的最少的天数。假如不能摘到 m 束花则回来 -1 。
 *
 * @example
 * 输入：bloomDay = [1,10,3,10,2], m = 3, k = 1
 * 输出：3
 */
const search_1482 = (bloomDay, m, k) => {
	const len = bloomDay.length;
	if (m * k > len) return -1;
	let [left, right] = [Math.min(...bloomDay), Math.max(...bloomDay)];
	while (left < right) {
		// 取中心天数
		const mid = Math.floor(left + (right - left) / 2);
		// 在mid地利，能否制造完
		if (check_3(bloomDay, mid, m, k)) {
			right = mid;
		} else {
			left = mid + 1;
		}
	}
	return left;
};
const check_1482 = (bloomDay, mid, m, k) => {
	let count = m;
	let can = 0;
	for (let i = 0; i < bloomDay.length && count >= 0; i++) {
		if (bloomDay[i] <= mid) {
			can++;
			if (can === k) {
				can = 0;
				count--;
			}
		} else {
			can = 0;
		}
	}
	return count <= 0;
};

lcp12 – 中等

小张刷题方案

/**
 * leetcode lcp12.小张刷题方案 - 中等
 *
 * @remarks
 * 为了进步自己的代码才能，小张拟定了 LeetCode 刷题方案，他选中了 LeetCode 题库中的 n 道题，编号从 0 到 n-1，并方案在 m 天内依照标题编号顺序刷完一切的标题（留意，小张不能用多天完结同一题）。
 * 在小张刷题方案中，小张需求用 time[i] 的时刻完结编号 i 的标题。此外，小张还能够运用场外求助功用，经过问询他的好朋友小杨标题的解法，能够省去该题的做题时刻。为了防止“小张刷题方案”变成“小杨刷题方案”，小张每天最多运用一次求助。
 * 咱们定义 m 天中做题时刻最多的一天耗时为 T（小杨完结的标题不计入做题总时刻）。请你帮小张求出最小的 T是多少。
 *
 * @example
 * 输入：time = [1,2,3,3,3], m = 2
 * 输出：3
 */
const search_lcp12 = (time, m) => {
	if (time.length === m) return 0;
	let [left, right] = [Math.min(...time), eval(time.join("+"))];
	while (left < right) {
		let mid = Math.floor(left + (right - left) / 2);
		// 最多耗时为mid时，m天内能否完结，能完结则向左缩短，不然右缩短
		if (check_4(time, mid, m)) {
			right = mid;
		} else {
			left = mid + 1;
		}
	}
	return left;
};
const check_lcp12 = (time, mid, m) => {
	const len = time.length;
	let total = 0;
	let count = 1;
	let max = time[0];
	for (let i = 0; i < len; i++) {
		max = time[i] >= max ? time[i] : max;
		let whole = total + time[i] - max;
		if (whole <= mid) {
			total += time[i];
		} else {
			count++;
			total = time[i];
			max = time[i];
		}
	}
	return count <= m;
};

最终

参阅文章：

leetcode官网
leetcode-weiwei

很感谢我们抽空读完这篇文章，希望我们能有所收获。祝我们作业顺利，身体健康。

下一篇：基础、高档、非比较排序算法。

「 ———- The end ———- 」

左中右，取整数，我叫「二分」你记住！🫵

减治思维

运用规模

二分下标

二分答案

处理思路

循环体中查找元素

循环体中扫除区间

实现细节

循环持续条件

取中心值法

中心值上下取整

lc例题

二分下标

35 – 简略

34 – 中等

153 – 中等

154 – 困难

33 – 中等

81 – 中等

278 – 简略

852 – 中等

1095 – 困难

4 – 困难

二分答案

69 – 简略

287 – 中等

1300 – 中等

复杂的判别条件

875 – 中等

410 – 困难

1011 – 中等

1482 – 中等

lcp12 – 中等

最终

作者信息

左中右，取整数，我叫「二分」你记住！🫵

减治思维

运用规模

二分下标

二分答案

处理思路

循环体中查找元素

循环体中扫除区间

实现细节

循环持续条件

取中心值法

中心值上下取整

lc例题

二分下标

35 – 简略

34 – 中等

153 – 中等

154 – 困难

33 – 中等

81 – 中等

278 – 简略

852 – 中等

1095 – 困难

4 – 困难

二分答案

69 – 简略

287 – 中等

1300 – 中等

复杂的判别条件

875 – 中等

410 – 困难

1011 – 中等

1482 – 中等

lcp12 – 中等

最终

相关文章

flutter web使用webviewBridge

面向大规模数据的云端管理，百度沧海存储产品解析

深入浅出 PLT/GOT Hook与原理实践

LeetCode – #80 删除有序数组中的重复项 II

作者信息