本文共 2160 字，大约阅读时间需要 7 分钟。
在这篇文章中，我们讨论了如何在已排序的数组中找到目标值的位置。我们将使用二分查找算法来实现这一目标，这种算法在已排序数组中搜索的效率远高于线性搜索。通过中间点条件，我们可以有效地缩小搜索范围，快速定位目标值或者确定插入位置。
二分查找算法的基本步骤可以总结如下：
初始化指针：设置数组的两个指针，begin 从数组起点 (0 )开始，end 从数组终点 (nums.length - 1) 开始。
进入循环：当 begin 小于等于 end 时，继续执行循环。
计算中间点：在当前 begin 和 end 区间中，计算中间点 mid。
比较目标值与中间值：
end 更新为 mid - 1。begin 更新为 mid + 1。mid。确定插入位置：如果整个循环结束后仍未找到目标值，说明目标值不存在于数组中。此时，需要返回目标值在已排序数组中应该插入的位置。这个位置将是 begin 的当前值，因为它已经超过了所有已知元素的右侧。
通过上述逻辑，我们可以编写如下的Java代码：
public class Solution { public int searchInsert(int[] nums, int target) { int begin = 0; int end = nums.length - 1; while (begin <= end) { int mid = (begin + end) / 2; if (target < nums[mid]) { end = mid - 1; } else if (target > nums[mid]) { begin = mid + 1; } else { return mid; } } return begin; }} 让我们通过一些测试用例来验证该算法的正确性。
示例1：数组：[1,3,5,6]目标值：5
begin=0，end=3mid = (0 + 3) / 2 = 1，nums[1]=3。因为5 > 3，begin 被设定为2。mid=(2 + 3)/2 = 2，nums[2]=5，与目标值相等，返回2。示例2：数组：[1,3,5,6]目标值：2
mid=1，nums[1]=3 > 2，所以将 end 设定为1-1=0。mid=0，nums[0]=1 < 2，所以将 end 设定为-1。循环结束后，返回 begin=1。示例3：数组：[1,3,5,6]目标值：7
mid=1，nums[1]=3 <7，begin 设为2。mid= (2+3)/2=2，nums[2]=5 <7，begin 设为3.mid=3，nums[3]=6 <7，所以 begin 被设定为4。begin >= end 时，返回4。示例4：数组：[1,3,5,6]目标值：0
mid=1，nums[1]=3 >0，所以 begin 被设定为1，进入下一个循环。mid=(1+3)/2=2，nums[2]=5 >0，继续将 begin 设定为3.mid=3，nums[3]=6 >0，begin 设定为4。begin=4 的值，哦，不对，这里期望的是返回0。这可能是一个测试案例中特殊情况的处理吗？让我重新审视一下。哦哦，原来如此，如果目标值比所有元素都小，那么循环结束时，begin 会被设定为数组的长度，就是4，那么返回4。这刚好符合插入位置是在前面所有元素之后的位置。但是对于示例4，输入是0，期望的输出是0，因为应该插入在第一个位置的前面。
那这个时候，我是不是哪里弄错了？看来原始代码可能需要再仔细检查一下。
再仔细思考示例4的情况：
输入数组是1,3,5,6，查找0，那么在所有元素前面。所以插入的位置应该是0。按照现有代码运行，什么时候会这样：
初始begin=0，end=3。先算mid=1，nums[1]=3，0<3，end=0.
接下来mid=0，nums[0]=1，0<1，end=-1，退出循环。return begin=0。这与期望结果一致。
哦，我的测试可能在更详细地思考中弄错了。那我再验证一下代码是否正确：
确实，示例4中的0比所有元素都小，所以每次都会进入 target < nums[mid] 的情况，直到 end=-1，返回begin=0。这样，代码是正确的。可能我在刚才的分析中错误地修改了代码，但实际上代码是正确的。
所以，以上代码在所有示例中都能正确工作。
转载地址：http://glhiz.baihongyu.com/