10.2 二分查找插入点¶
二分查找不仅可用于搜索目标元素,还可用于解决许多变种问题,比如搜索目标元素的插入位置。
10.2.1 无重复元素的情况¶
Question
给定一个长度为 \(n\) 的有序数组 nums 和一个元素 target ,数组不存在重复元素。现将 target 插入数组 nums 中,并保持其有序性。若数组中已存在元素 target ,则插入到其左方。请返回插入后 target 在数组中的索引。示例如图 10-4 所示。
图 10-4 二分查找插入点示例数据
图解 10-4:有序数组的插入位置
在已有元素的左侧插入相等的新值,保持数组有序。
初始无重复元素的有序数组为 nums = [1, 3, 6, 8, 12, 15, 23, 26, 31, 35],待插入目标元素为 target = 6。题目约定插入后保持数组有序;若数组中已存在与 target 相等的元素,则将新元素插入到相等元素的左方。
画面上行展示原始数组 nums,在元素 3(索引 1)与原有元素 6(索引 2)之间的缝隙下方标出向上的“插入点”箭头,注明 target 的插入点索引为 2。
经中间向下的“插入 target”粗箭头过渡后,下行展示插入完成后的 11 元素数组 [1, 3, 6, 6, 8, 12, 15, 23, 26, 31, 35]:青色高亮的 6 是新插入的元素,占据索引 2;原有的绿色 6 及其右侧所有元素整体向右平移一位,原有 6 的索引变为 3。
本例初始数组无重复值,已有 target 的位置就是插入点;插入后可以出现相等元素。
如果想复用上一节的二分查找代码,则需要回答以下两个问题。
问题一:当数组中包含 target 时,插入点的索引是否是该元素的索引?
题目要求将 target 插入到相等元素的左边,这意味着新插入的 target 替换了原来 target 的位置。也就是说,当数组包含 target 时,插入点的索引就是该 target 的索引。
问题二:当数组中不存在 target 时,插入点是哪个元素的索引?
进一步思考二分查找过程:当 nums[m] < target 时 \(i\) 移动,这意味着指针 \(i\) 在向大于等于 target 的元素靠近。同理,指针 \(j\) 始终在向小于等于 target 的元素靠近。
因此二分结束时一定有:\(i\) 指向首个大于 target 的元素,\(j\) 指向最右一个小于 target 的元素。易得当数组不包含 target 时,插入索引为 \(i\) 。代码如下所示:
def binary_search_insertion_simple(nums: list[int], target: int) -> int:
"""二分查找插入点(无重复元素)"""
i, j = 0, len(nums) - 1 # 初始化双闭区间 [0, n-1]
while i <= j:
m = (i + j) // 2 # 计算中点索引 m
if nums[m] < target:
i = m + 1 # target 在区间 [m+1, j] 中
elif nums[m] > target:
j = m - 1 # target 在区间 [i, m-1] 中
else:
return m # 找到 target ,返回插入点 m
# 未找到 target ,返回插入点 i
return i
/* 二分查找插入点(无重复元素) */
int binarySearchInsertionSimple(vector<int> &nums, int target) {
int i = 0, j = nums.size() - 1; // 初始化双闭区间 [0, n-1]
while (i <= j) {
int m = i + (j - i) / 2; // 计算中点索引 m
if (nums[m] < target) {
i = m + 1; // target 在区间 [m+1, j] 中
} else if (nums[m] > target) {
j = m - 1; // target 在区间 [i, m-1] 中
} else {
return m; // 找到 target ,返回插入点 m
}
}
// 未找到 target ,返回插入点 i
return i;
}
/* 二分查找插入点(无重复元素) */
int binarySearchInsertionSimple(int[] nums, int target) {
int i = 0, j = nums.length - 1; // 初始化双闭区间 [0, n-1]
while (i <= j) {
int m = i + (j - i) / 2; // 计算中点索引 m
if (nums[m] < target) {
i = m + 1; // target 在区间 [m+1, j] 中
} else if (nums[m] > target) {
j = m - 1; // target 在区间 [i, m-1] 中
} else {
return m; // 找到 target ,返回插入点 m
}
}
// 未找到 target ,返回插入点 i
return i;
}
/* 二分查找插入点(无重复元素) */
int BinarySearchInsertionSimple(int[] nums, int target) {
int i = 0, j = nums.Length - 1; // 初始化双闭区间 [0, n-1]
while (i <= j) {
int m = i + (j - i) / 2; // 计算中点索引 m
if (nums[m] < target) {
i = m + 1; // target 在区间 [m+1, j] 中
} else if (nums[m] > target) {
j = m - 1; // target 在区间 [i, m-1] 中
} else {
return m; // 找到 target ,返回插入点 m
}
}
// 未找到 target ,返回插入点 i
return i;
}
/* 二分查找插入点(无重复元素) */
func binarySearchInsertionSimple(nums []int, target int) int {
// 初始化双闭区间 [0, n-1]
i, j := 0, len(nums)-1
for i <= j {
// 计算中点索引 m
m := i + (j-i)/2
if nums[m] < target {
// target 在区间 [m+1, j] 中
i = m + 1
} else if nums[m] > target {
// target 在区间 [i, m-1] 中
j = m - 1
} else {
// 找到 target ,返回插入点 m
return m
}
}
// 未找到 target ,返回插入点 i
return i
}
/* 二分查找插入点(无重复元素) */
func binarySearchInsertionSimple(nums: [Int], target: Int) -> Int {
// 初始化双闭区间 [0, n-1]
var i = nums.startIndex
var j = nums.endIndex - 1
while i <= j {
let m = i + (j - i) / 2 // 计算中点索引 m
if nums[m] < target {
i = m + 1 // target 在区间 [m+1, j] 中
} else if nums[m] > target {
j = m - 1 // target 在区间 [i, m-1] 中
} else {
return m // 找到 target ,返回插入点 m
}
}
// 未找到 target ,返回插入点 i
return i
}
/* 二分查找插入点(无重复元素) */
function binarySearchInsertionSimple(nums, target) {
let i = 0,
j = nums.length - 1; // 初始化双闭区间 [0, n-1]
while (i <= j) {
const m = Math.floor(i + (j - i) / 2); // 计算中点索引 m, 使用 Math.floor() 向下取整
if (nums[m] < target) {
i = m + 1; // target 在区间 [m+1, j] 中
} else if (nums[m] > target) {
j = m - 1; // target 在区间 [i, m-1] 中
} else {
return m; // 找到 target ,返回插入点 m
}
}
// 未找到 target ,返回插入点 i
return i;
}
/* 二分查找插入点(无重复元素) */
function binarySearchInsertionSimple(
nums: Array<number>,
target: number
): number {
let i = 0,
j = nums.length - 1; // 初始化双闭区间 [0, n-1]
while (i <= j) {
const m = Math.floor(i + (j - i) / 2); // 计算中点索引 m, 使用 Math.floor() 向下取整
if (nums[m] < target) {
i = m + 1; // target 在区间 [m+1, j] 中
} else if (nums[m] > target) {
j = m - 1; // target 在区间 [i, m-1] 中
} else {
return m; // 找到 target ,返回插入点 m
}
}
// 未找到 target ,返回插入点 i
return i;
}
/* 二分查找插入点(无重复元素) */
int binarySearchInsertionSimple(List<int> nums, int target) {
int i = 0, j = nums.length - 1; // 初始化双闭区间 [0, n-1]
while (i <= j) {
int m = i + (j - i) ~/ 2; // 计算中点索引 m
if (nums[m] < target) {
i = m + 1; // target 在区间 [m+1, j] 中
} else if (nums[m] > target) {
j = m - 1; // target 在区间 [i, m-1] 中
} else {
return m; // 找到 target ,返回插入点 m
}
}
// 未找到 target ,返回插入点 i
return i;
}
/* 二分查找插入点(无重复元素) */
fn binary_search_insertion_simple(nums: &[i32], target: i32) -> i32 {
let (mut i, mut j) = (0, nums.len() as i32 - 1); // 初始化双闭区间 [0, n-1]
while i <= j {
let m = i + (j - i) / 2; // 计算中点索引 m
if nums[m as usize] < target {
i = m + 1; // target 在区间 [m+1, j] 中
} else if nums[m as usize] > target {
j = m - 1; // target 在区间 [i, m-1] 中
} else {
return m;
}
}
// 未找到 target ,返回插入点 i
i
}
/* 二分查找插入点(无重复元素) */
int binarySearchInsertionSimple(int *nums, int numSize, int target) {
int i = 0, j = numSize - 1; // 初始化双闭区间 [0, n-1]
while (i <= j) {
int m = i + (j - i) / 2; // 计算中点索引 m
if (nums[m] < target) {
i = m + 1; // target 在区间 [m+1, j] 中
} else if (nums[m] > target) {
j = m - 1; // target 在区间 [i, m-1] 中
} else {
return m; // 找到 target ,返回插入点 m
}
}
// 未找到 target ,返回插入点 i
return i;
}
/* 二分查找插入点(无重复元素) */
fun binarySearchInsertionSimple(nums: IntArray, target: Int): Int {
var i = 0
var j = nums.size - 1 // 初始化双闭区间 [0, n-1]
while (i <= j) {
val m = i + (j - i) / 2 // 计算中点索引 m
if (nums[m] < target) {
i = m + 1 // target 在区间 [m+1, j] 中
} else if (nums[m] > target) {
j = m - 1 // target 在区间 [i, m-1] 中
} else {
return m // 找到 target ,返回插入点 m
}
}
// 未找到 target ,返回插入点 i
return i
}
### 二分查找插入点(无重复元素) ###
def binary_search_insertion_simple(nums, target)
# 初始化双闭区间 [0, n-1]
i, j = 0, nums.length - 1
while i <= j
# 计算中点索引 m
m = (i + j) / 2
if nums[m] < target
i = m + 1 # target 在区间 [m+1, j] 中
elsif nums[m] > target
j = m - 1 # target 在区间 [i, m-1] 中
else
return m # 找到 target ,返回插入点 m
end
end
i # 未找到 target ,返回插入点 i
end
可视化运行
10.2.2 存在重复元素的情况¶
Question
在上一题的基础上,规定数组可能包含重复元素,其余不变。
假设数组中存在多个 target ,则普通二分查找只能返回其中一个 target 的索引,而无法确定该元素的左边和右边还有多少 target。
题目要求将目标元素插入到最左边,所以我们需要查找数组中最左一个 target 的索引。初步考虑通过图 10-5 所示的步骤实现。
- 执行二分查找,得到任意一个
target的索引,记为 \(k\) 。 - 从索引 \(k\) 开始,向左进行线性遍历,当找到最左边的
target时返回。
图 10-5 线性查找重复元素的插入点
图解 10-5:二分命中后向左回退
先用普通二分找到一个目标,再向左线性扫描确定最左位置。
有序数组 nums = [1, 3, 6, 6, 6, 6, 6, 10, 12, 15](索引从 0 开始),查找目标为 target = 6。数组中索引 2 至 6 连续分布着五个重复的 6,插入规则要求将新 6 插入到所有已有 6 的最左方。
画面分两步演示初步思路:第一步“1. 先二分查找到任意一个 6”,普通二分查找命中位于索引 4 的橙色方格(标有指针 k),但仅凭这次命中无法得知它左侧还有多少个相等的 6。
第二步“2. 再线性查找到最左边的 6”,从索引 k = 4 出发,沿数组下方的两段蓝色弧线箭头逐格向左回退:先经过索引 3 的 6,再到达索引 2 的蓝色高亮方格 6。由于再往左的索引 1 元素为 3(小于 6),可知索引 2 即为最左一个 6 的位置,也就是所求插入点。
向左线性扫描在重复元素很多时可能耗时 O(n),使整体最坏复杂度退化;改进二分可保持 O(log n)。
此方法虽然可用,但其包含线性查找,因此时间复杂度为 \(O(n)\) 。当数组中存在很多重复的 target 时,该方法效率很低。
现考虑拓展二分查找代码。如图 10-6 所示,整体流程保持不变,每轮先计算中点索引 \(m\) ,再判断 target 和 nums[m] 的大小关系,分为以下几种情况。
- 当
nums[m] < target或nums[m] > target时,说明还没有找到target,因此采用普通二分查找的缩小区间操作,从而使指针 \(i\) 和 \(j\) 向target靠近。 - 当
nums[m] == target时,说明小于target的元素在区间 \([i, m - 1]\) 中,因此采用 \(j = m - 1\) 来缩小区间,从而使指针 \(j\) 向小于target的元素靠近。
循环完成后,\(i\) 指向最左边的 target ,\(j\) 指向最右一个小于 target 的元素,因此索引 \(i\) 就是插入点。
图 10-6 二分查找重复元素的插入点的步骤
图解 10-6:二分查找最左插入点
中点等于目标时继续向左查找,确定所有相等元素之前的插入位置。
给定升序数组 [1, 3, 6, 6, 6, 6, 6, 10, 12, 15],索引为 0 至 9,查找目标值 target = 6 的插入点。值 6 连续占据索引 2 至 6;题目要求返回新 6 应插入的索引,使它排在所有已有 6 的最左侧(本算法仅计算并返回插入点索引,不在原数组中实际执行插入搬移)。
指针 i、j 表示双闭搜索区间 [i, j] 的左、右边界,中点索引按 m = (i + j) / 2 向下取整计算。当 nums[m] < target 时执行 i = m + 1 向右逼近;当 nums[m] > target 或 nums[m] == target 时均执行 j = m − 1 向左收缩,使指针 j 持续逼近小于 target 的最右元素、指针 i 持续逼近首个大于等于 target 的位置。
每轮先计算中点,再移动一个边界。边界刚更新时,图中的 m 仍是上一次的中点,可能留在新区间之外;只有再次计算中点时才更新 m。
下面先列固定输入,再用一张表汇总八帧的指针轨迹,之后的各步说明给出操作原因和当前状态。八帧对应三轮中点比较,不是八轮循环。
| 索引 | 值 |
|---|---|
| 0 | 1 |
| 1 | 3 |
| 2 | 6 |
| 3 | 6 |
| 4 | 6 |
| 5 | 6 |
| 6 | 6 |
| 7 | 10 |
| 8 | 12 |
| 9 | 15 |
| 步骤 | i | j | m | 搜索区间 | 中点或返回状态 |
|---|---|---|---|---|---|
| 1 | 0 | 9 | 未计算 | [0, 9] | 未计算 |
| 2 | 0 | 9 | 4 | [0, 9] | 本轮中点 |
| 3 | 0 | 3 | 4 | [0, 3] | 旧中点,在新区间右侧之外 |
| 4 | 0 | 3 | 1 | [0, 3] | 本轮中点 |
| 5 | 2 | 3 | 1 | [2, 3] | 旧中点,在新区间左侧之外 |
| 6 | 2 | 3 | 2 | [2, 3] | 本轮中点 |
| 7 | 2 | 1 | 2 | [2, 1],空区间 | 旧中点,区间已空,不再重算 |
| 8 | 2 | 图中不再显示 | 图中不再显示 | 搜索结束 | 仅显示返回指针 i |
初始化搜索区间
目标值为 6。初始化 i = 0,j = 9,双闭区间 [0, 9] 覆盖全部十个元素,尚未计算 m;数组见“固定输入:目标值为 6”。
计算中点 4
第 1 轮:当前 i = 0,j = 9,对区间 [0, 9] 计算 m = (0 + 9) // 2 = 4。nums[4] = 6 等于目标,但还不能确定它是最左一个 6。
遇到 6,右边界左移
nums[4] = 6 等于目标,为排查左侧是否还有 6,执行 j = m − 1。当前 i = 0,j = 3,区间为 [0, 3];图中 m = 4 是未重算的旧中点,留在新区间右侧之外。
计算中点 1
第 2 轮:当前 i = 0,j = 3,对区间 [0, 3] 重算 m = (0 + 3) // 2 = 1。nums[1] = 3 小于目标 6,插入点在它右侧。
遇到 3,左边界右移
因 nums[1] = 3 小于目标 6,执行 i = m + 1。当前 i = 2,j = 3,区间为 [2, 3];图中 m = 1 是未重算的旧中点,留在新区间左侧之外。
计算中点 2
第 3 轮:当前 i = 2,j = 3,对区间 [2, 3] 重算 m = (2 + 3) // 2 = 2。nums[2] = 6 再次等于目标。
再次遇到 6,区间变空
因 nums[2] = 6 等于目标,继续执行 j = m − 1。当前 i = 2,j = 1,双闭区间 [2, 1] 已空,循环将结束;图中仍保留旧中点 m = 2,不再重算。
返回最左插入索引 2
循环结束,图中仅保留返回指针 i = 2,j、m 不再显示。返回索引 2,使新 6 排在已有五个 6 之前;原数组没有发生插入或搬移。
观察以下代码,判断分支 nums[m] > target 和 nums[m] == target 的操作相同,因此两者可以合并。
即便如此,我们仍然可以将判断条件保持展开,因为其逻辑更加清晰、可读性更好。
def binary_search_insertion(nums: list[int], target: int) -> int:
"""二分查找插入点(存在重复元素)"""
i, j = 0, len(nums) - 1 # 初始化双闭区间 [0, n-1]
while i <= j:
m = (i + j) // 2 # 计算中点索引 m
if nums[m] < target:
i = m + 1 # target 在区间 [m+1, j] 中
elif nums[m] > target:
j = m - 1 # target 在区间 [i, m-1] 中
else:
j = m - 1 # 最右一个小于 target 的元素在区间 [i, m-1] 中
# 返回插入点 i
return i
/* 二分查找插入点(存在重复元素) */
int binarySearchInsertion(vector<int> &nums, int target) {
int i = 0, j = nums.size() - 1; // 初始化双闭区间 [0, n-1]
while (i <= j) {
int m = i + (j - i) / 2; // 计算中点索引 m
if (nums[m] < target) {
i = m + 1; // target 在区间 [m+1, j] 中
} else if (nums[m] > target) {
j = m - 1; // target 在区间 [i, m-1] 中
} else {
j = m - 1; // 最右一个小于 target 的元素在区间 [i, m-1] 中
}
}
// 返回插入点 i
return i;
}
/* 二分查找插入点(存在重复元素) */
int binarySearchInsertion(int[] nums, int target) {
int i = 0, j = nums.length - 1; // 初始化双闭区间 [0, n-1]
while (i <= j) {
int m = i + (j - i) / 2; // 计算中点索引 m
if (nums[m] < target) {
i = m + 1; // target 在区间 [m+1, j] 中
} else if (nums[m] > target) {
j = m - 1; // target 在区间 [i, m-1] 中
} else {
j = m - 1; // 最右一个小于 target 的元素在区间 [i, m-1] 中
}
}
// 返回插入点 i
return i;
}
/* 二分查找插入点(存在重复元素) */
int BinarySearchInsertion(int[] nums, int target) {
int i = 0, j = nums.Length - 1; // 初始化双闭区间 [0, n-1]
while (i <= j) {
int m = i + (j - i) / 2; // 计算中点索引 m
if (nums[m] < target) {
i = m + 1; // target 在区间 [m+1, j] 中
} else if (nums[m] > target) {
j = m - 1; // target 在区间 [i, m-1] 中
} else {
j = m - 1; // 最右一个小于 target 的元素在区间 [i, m-1] 中
}
}
// 返回插入点 i
return i;
}
/* 二分查找插入点(存在重复元素) */
func binarySearchInsertion(nums []int, target int) int {
// 初始化双闭区间 [0, n-1]
i, j := 0, len(nums)-1
for i <= j {
// 计算中点索引 m
m := i + (j-i)/2
if nums[m] < target {
// target 在区间 [m+1, j] 中
i = m + 1
} else if nums[m] > target {
// target 在区间 [i, m-1] 中
j = m - 1
} else {
// 最右一个小于 target 的元素在区间 [i, m-1] 中
j = m - 1
}
}
// 返回插入点 i
return i
}
/* 二分查找插入点(存在重复元素) */
func binarySearchInsertion(nums: [Int], target: Int) -> Int {
// 初始化双闭区间 [0, n-1]
var i = nums.startIndex
var j = nums.endIndex - 1
while i <= j {
let m = i + (j - i) / 2 // 计算中点索引 m
if nums[m] < target {
i = m + 1 // target 在区间 [m+1, j] 中
} else if nums[m] > target {
j = m - 1 // target 在区间 [i, m-1] 中
} else {
j = m - 1 // 最右一个小于 target 的元素在区间 [i, m-1] 中
}
}
// 返回插入点 i
return i
}
/* 二分查找插入点(存在重复元素) */
function binarySearchInsertion(nums, target) {
let i = 0,
j = nums.length - 1; // 初始化双闭区间 [0, n-1]
while (i <= j) {
const m = Math.floor(i + (j - i) / 2); // 计算中点索引 m, 使用 Math.floor() 向下取整
if (nums[m] < target) {
i = m + 1; // target 在区间 [m+1, j] 中
} else if (nums[m] > target) {
j = m - 1; // target 在区间 [i, m-1] 中
} else {
j = m - 1; // 最右一个小于 target 的元素在区间 [i, m-1] 中
}
}
// 返回插入点 i
return i;
}
/* 二分查找插入点(存在重复元素) */
function binarySearchInsertion(nums: Array<number>, target: number): number {
let i = 0,
j = nums.length - 1; // 初始化双闭区间 [0, n-1]
while (i <= j) {
const m = Math.floor(i + (j - i) / 2); // 计算中点索引 m, 使用 Math.floor() 向下取整
if (nums[m] < target) {
i = m + 1; // target 在区间 [m+1, j] 中
} else if (nums[m] > target) {
j = m - 1; // target 在区间 [i, m-1] 中
} else {
j = m - 1; // 最右一个小于 target 的元素在区间 [i, m-1] 中
}
}
// 返回插入点 i
return i;
}
/* 二分查找插入点(存在重复元素) */
int binarySearchInsertion(List<int> nums, int target) {
int i = 0, j = nums.length - 1; // 初始化双闭区间 [0, n-1]
while (i <= j) {
int m = i + (j - i) ~/ 2; // 计算中点索引 m
if (nums[m] < target) {
i = m + 1; // target 在区间 [m+1, j] 中
} else if (nums[m] > target) {
j = m - 1; // target 在区间 [i, m-1] 中
} else {
j = m - 1; // 最右一个小于 target 的元素在区间 [i, m-1] 中
}
}
// 返回插入点 i
return i;
}
/* 二分查找插入点(存在重复元素) */
pub fn binary_search_insertion(nums: &[i32], target: i32) -> i32 {
let (mut i, mut j) = (0, nums.len() as i32 - 1); // 初始化双闭区间 [0, n-1]
while i <= j {
let m = i + (j - i) / 2; // 计算中点索引 m
if nums[m as usize] < target {
i = m + 1; // target 在区间 [m+1, j] 中
} else if nums[m as usize] > target {
j = m - 1; // target 在区间 [i, m-1] 中
} else {
j = m - 1; // 最右一个小于 target 的元素在区间 [i, m-1] 中
}
}
// 返回插入点 i
i
}
/* 二分查找插入点(存在重复元素) */
int binarySearchInsertion(int *nums, int numSize, int target) {
int i = 0, j = numSize - 1; // 初始化双闭区间 [0, n-1]
while (i <= j) {
int m = i + (j - i) / 2; // 计算中点索引 m
if (nums[m] < target) {
i = m + 1; // target 在区间 [m+1, j] 中
} else if (nums[m] > target) {
j = m - 1; // target 在区间 [i, m-1] 中
} else {
j = m - 1; // 最右一个小于 target 的元素在区间 [i, m-1] 中
}
}
// 返回插入点 i
return i;
}
/* 二分查找插入点(存在重复元素) */
fun binarySearchInsertion(nums: IntArray, target: Int): Int {
var i = 0
var j = nums.size - 1 // 初始化双闭区间 [0, n-1]
while (i <= j) {
val m = i + (j - i) / 2 // 计算中点索引 m
if (nums[m] < target) {
i = m + 1 // target 在区间 [m+1, j] 中
} else if (nums[m] > target) {
j = m - 1 // target 在区间 [i, m-1] 中
} else {
j = m - 1 // 最右一个小于 target 的元素在区间 [i, m-1] 中
}
}
// 返回插入点 i
return i
}
### 二分查找插入点(存在重复元素) ###
def binary_search_insertion(nums, target)
# 初始化双闭区间 [0, n-1]
i, j = 0, nums.length - 1
while i <= j
# 计算中点索引 m
m = (i + j) / 2
if nums[m] < target
i = m + 1 # target 在区间 [m+1, j] 中
elsif nums[m] > target
j = m - 1 # target 在区间 [i, m-1] 中
else
j = m - 1 # 最右一个小于 target 的元素在区间 [i, m-1] 中
end
end
i # 返回插入点 i
end
可视化运行
Tip
本节的代码都是“双闭区间”写法。有兴趣的读者可以自行实现“左闭右开”写法。
总的来看,二分查找无非就是给指针 \(i\) 和 \(j\) 分别设定搜索目标,目标可能是一个具体的元素(例如 target ),也可能是一个元素范围(例如小于 target 的元素)。
在不断的循环二分中,指针 \(i\) 和 \(j\) 都逐渐逼近预先设定的目标。最终,它们或是成功找到答案,或是越过边界后停止。