让我们通过一个具体的例子来详细解释二分查找的过程，并通过文本图形化的方式来描述每一步的变化。假设我们有一个数组 nums = [-1, 0, 3, 5, 9, 12] 并且目标值 target = 9。
初始状态
- 数组：
[-1, 0, 3, 5, 9, 12] - 目标值：
9 - 左指针
left = 0 - 右指针
right = 5(数组长度减1) - 中间位置
mid = (0 + 5) / 2 = 2(索引为2的元素是3)
索引： 0 1 2 3 4 5
初始数组： -1 0 3 5 9 12
↑ ↑ ↑
left mid right
第一次循环
nums[mid] = 3小于target = 9，因此需要调整左指针。- 更新左指针
left = mid + 1 = 3。
索引： 0 1 2 3 4 5
第一次循环后： -1 0 3 5 9 12
↑ ↑ ↑
left mid right
第二次循环
- 更新中间位置
mid = (3 + 5) / 2 = 4(索引为4的元素是9) nums[mid] = 9等于target = 9，找到目标值，返回索引4。
索引： 0 1 2 3 4 5
第二次循环后： -1 0 3 5 9 12
↑
mid
结果
- 目标值
9的索引为4。
这个文本图形化的描述显示了如何通过二分查找逐步缩小搜索范围，直到找到目标值。在每次循环中，我们都会根据中间值和目标值的比较结果来调整搜索范围，直到成功找到目标值或确定目标值不存在于数组中。
更复杂的例子
让我们考虑一个稍微复杂的情况，以进一步解释二分查找的过程。假设我们有一个数组 nums = [-10, -3, 0, 5, 9, 12, 14, 17, 19, 23, 29] 并且目标值 target = 0。
初始状态
- 数组：
[-10, -3, 0, 5, 9, 12, 14, 17, 19, 23, 29] - 目标值：
0 - 左指针
left = 0 - 右指针
right = 10(数组长度减1) - 中间位置
mid = (0 + 10) / 2 = 5(索引为5的元素是12)
索引： 0 1 2 3 4 5 6 7 8 9 10
初始数组： -10 -3 0 5 9 12 14 17 19 23 29
↑ ↑ ↑
left mid right
第一次循环
nums[mid] = 12大于target = 0，需要调整右指针。- 更新右指针
right = mid - 1 = 4。
索引： 0 1 2 3 4 5 6 7 8 9 10
第一次循环后： -10 -3 0 5 9 12 14 17 19 23 29
↑ ↑
left right
(mid 更新后将位于 left 和 right 的中间)
第二次循环
- 更新中间位置
mid = (0 + 4) / 2 = 2(索引为2的元素是0) nums[mid] = 0等于target = 0，找到目标值，返回索引2。
索引： 0 1 2 3 4 5 6 7 8 9 10
第二次循环后： -10 -3 0 5 9 12 14 17 19 23 29
↑
mid
结果
- 目标值
0的索引为2。
在这个更复杂的例子中，我们看到了二分查找如何在一个更大的数组中有效地定位目标值。通过每次比较中间元素与目标值，并相应地调整搜索范围的边界，二分查找算法能够快速缩小搜索区域，直到找到目标值或确定目标值不在数组中。这种方法特别适用于大型有序数组，因为它大大减少了必须比较的元素数量，从而提高了搜索效率。
代码
下面是一个易于理解的C++代码实现：
class Solution {
public:
int search(vector<int>& nums, int target) {
// 初始化两个指针，i（左指针）和j（右指针），分别指向数组的起始和结束位置
int i = 0, j = nums.size() - 1;
// 当左指针不大于右指针时，执行循环
while (i <= j) {
// 计算中间位置的索引mid。这里使用i + (j - i) / 2来避免直接使用(i + j) / 2可能导致的整数溢出问题
int mid = i + (j - i) / 2;
// 如果中间位置的元素小于目标值，说明目标值在数组的右半部分
if (nums[mid] < target) {
// 因此，调整左指针i到中间位置的右侧，即mid + 1
i = mid + 1;
}
// 如果中间位置的元素大于目标值，说明目标值在数组的左半部分
else if (nums[mid] > target){
// 因此，调整右指针j到中间位置的左侧，即mid - 1
j = mid - 1;
}
// 如果中间位置的元素正好等于目标值
else {
// 直接返回该位置的索引
return mid;
}
}
// 如果循环结束还没有找到目标值，说明目标值不在数组中，返回-1
return -1;
}
};
这段代码首先初始化左右指针分别指向数组的开始和结束位置。然后，它进入一个循环，在循环中计算中间位置的索引 mid 并将 mid 位置上的元素与目标值 target 进行比较。如果找到目标值，则返回其索引；如果 mid 位置上的元素小于目标值，则调整左指针 left 到 mid + 1；如果 mid 位置上的元素大于目标值，则调整右指针 right 到 mid - 1。如果在数组中找不到目标值，则最终返回 -1。