一、二分基础知识
1. 概念
在一个长度为 n 的数组中查找一个数字，如果逐一扫描数组中的每 个数字，那么需要 O(n) 的时间。
如果数组是排序的（通常按照递增的顺序排序），那么可以采用 二分查找算法进行优化。可以取出位于数组中间的数字并和目标数字比较。如果中间数字正好等于目标数字，那么就找到了目标数字。如果中间数字大于目标数字，那么只需要查找数组的前半部分，这是因为数组是排序的，后半部分的数字都大于或等于中间数字，所以一定都大于目标数字，也就没有必要再在后半部分查找。如果中间数字小于目标数字，那么接下来只需要查找数组的后半部分，这是因为排序数组的前半部分的数字都小于或等于中间数字，所以一定都小于目标数字，也就没有必要再在前半部分查找。
参考代码如下：
public static int search(int[] nums, int target) {
int start = 0, end = nums.length - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return -1;
}
二、二分知识扩展
1. 排序数组中的二分
知识扩展
在数组中查找一个数字原本是一件非常直观的事情，逐一扫描数组中的数字即可。但如果数组是有序的集合，那么非常建议使用二分查找进行处理。
题目练习
Ⅰ：查找插入位置
题目描述
略输入一个排序的整数数组 nums 和一个目标值 t ，如果数组 nums 中包含 t ，则返回 t 在数组中的下标；如果数组 nums 中不包含 t ，则返回将 t 按顺序插入数组 nums 中的下标。假设数组中没有相同的数字。例如，输入数组 nums 为 [1，3，6，8]，如果目标值 t 为 3，则输出1；如果 t 为 5，则返回 2。
题目分析
难度： ⭐🐇🐇🐇🐇
思路：
这是一个典型的二分查找题目，不同在于，找不到相同元素时需要返回插入的下标位置。分析二分查找代码不难发现，start 其实记录的正好就是这个需要插入的下标，即只需要将最后的 return -1 更换为 return start。
因为在找不到目标元素时，start 和 end 一定会在最接近目标的元素的旁边相遇，相遇时，我们所需要求得的下标便是相遇位置左移或者右移一位的下标位置，当相遇的位置所处元素值小于目标元素，那么插入下标应该是当前下标的下一位，而此时 start 正好右移；而如果大于目标元素时，说明应该在当前位置插入，而此时 start 正好不移动，所以此时二分查找后 start 就是应该插入的位置下标。
当然可以从边界条件进行分析，如果 mid 指向元素 < 目标元素，那么目标位置一定在 mid + 1 --> end 之中；如果 mid 指向元素 >= 目标元素，且 mid - 1 指向元素 < 目标元素，那么 mid 即为所求；如果此时 mid - 1 不满足，则所求元素一定在 start --> mid -1 之中。
参考代码
// 二分改
public static int findIndex(int[] nums, int target) {
int start = 0, end = nums.length - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return start;
}
// 另一种思路
public static int findIndex2(int[] nums, int target) {
int start = 0, end = nums.length - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (nums[mid] >= target) {
// mid = 0 表示数组元素都大于目标
if (mid == 0 || nums[mid - 1] < target) {
return mid;
}
end = mid - 1;
} else {
start = mid + 1;
}
}
// 数组元素都小于目标时，返回长度即可
return nums.length;
}
Tips：2025-06-20
Ⅱ：山峰数组的顶部
题目描述
在一个长度大于或等于 3 的数组中，任意相邻的两个数字都不相等。该数组的前若干数字是递增的，之后的数字是递减的，因此它的值看起来像一座山峰。请找出山峰顶部，即数组中最大值的位置。例如，在数组 [1，3，5，4，2] 中，最大值是 5，输出它在数组中的下标 2。
题目分析
难度： ⭐🐇🐇🐇🐇
思路： 暴力的方式暂不说明；这依旧是一个二分的典型题目，只不过确认确认范围的条件有所改变，我们需要根据元素的前一个元素和后一个元素确定，当前元素是属于递增部分还是递减部分，如果是递增部分，那么峰值一定在 mid + 1 --> end 之中，否则一定在 start --> mid - 1 之中；而如果元素的前一个元素小于自己，后一个元素也小于自己，那么当前元素即为所求。
参考代码
public static int findTopIndex(int[] nums) {
// 由于求的是峰值，那么元素数量一定大于 1，左右边界可以往中间靠 1
int start = 1, end = nums.length - 2;
while (start <= end) {
int mid = (start + end) / 2;
if (nums[mid] > nums[mid + 1] && nums[mid] > nums[mid - 1]) {
return mid;
}
if (nums[mid] > nums[mid + 1]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return -1;
}
Tips：2025-06-20
Ⅲ：排序数组中只出现一次的数字
题目描述
在一个排序的数组中，除一个数字只出现一次之外，其他数字都出现了两次，请找出这个唯一只出现一次的数字。例如，在数组 [1，1，2，2，3，4，4，5，5] 中，数字 3 只出现了一次。
题目分析
难度： ⭐⭐🐇🐇🐇
思路： 如果不存在出现依次的元素，那么两两进行分组时，各组内元素一定相同。而加入出现一次的元素后，从该元素开始，后续的组合两元素将不再相同。此时如果找到第一次两元素不同的组合后，改组合的首元素即为所求。判断是否为第一次出现差异的组的依据便是前一组的两个元素相等。
参考代码
public int findSingleIndex(int[] nums) {
// 将数组两两分组，而比较元素时乘以 2 得出原下标
int start = 0, end = nums.length / 2;
while (start <= end) {
int mid = (start + end) / 2;
int i = mid * 2;
if (i < nums.length - 1 && nums[i] != nums[i + 1]) {
// 如果前一组值相等，说明当前组为第一组出现不同的组合
if (mid == 0 || nums[mid - 2] == nums[i - 1]) {
return nums[i];
}
end = mid - 1;
} else {
start = mid + 1;
}
}
return nums[nums.length - 1];
}
Tips：2025-06-20
Ⅳ：按权重生成随机数
题目描述
输入一个正整数数组 w，数组中的每个数字 w[i] 表示下标 i 的权重，请实现一个函数 pickIndex 根据权重比例随机选择一个下标。例如，如果权重数组 w 为 [1，2，3，4]，那么函数 pickIndex 将有 10% 的概率选择 0、20% 的概率选择 1、30% 的概率选择 2、40% 的概率选择 3。
题目分析
难度： 略
思路： 略
参考代码
Tips：-
2. 数值范围内的二分
知识扩展
略
题目练习
Ⅰ：求平方根
题目描述
输入一个非负整数，请计算它的平方根。正数的平方根有两个，只输出其中的正数平方根。如果平方根不是整数，那么只需要输出它的整数部分。例如，如果输入 4 则输出 2；如果输入18 则输出 4。
题目分析
难度： 略
思路： 略
参考代码
Tips：-
Ⅱ：狒狒吃香蕉
题目描述
狒狒很喜欢吃香蕉。一天它发现了 n 堆香蕉，第 i 堆有 piles[i] 根香蕉。门卫刚好走开，H 小时后才会回来。狒狒吃香蕉喜欢细嚼慢咽，但又想在门卫回来之前吃完所有的香蕉。请问狒狒每小时至少吃多少根香蕉？如果狒狒决定每小时吃 k 根香蕉，而它在吃的某一堆剩余的香蕉的数目少于 k，那么它只会将这一堆的香蕉吃完，下一个小时才会开始吃另一堆的香蕉。
题目分析
难度： 略
思路： 略
参考代码
Tips：-
三、章节小结
略