本文共 2160 字，大约阅读时间需要 7 分钟。

在这篇文章中，我们讨论了如何在已排序的数组中找到目标值的位置。我们将使用二分查找算法来实现这一目标，这种算法在已排序数组中搜索的效率远高于线性搜索。通过中间点条件，我们可以有效地缩小搜索范围，快速定位目标值或者确定插入位置。

二分查找方法

二分查找算法的基本步骤可以总结如下：

代码实现

通过上述逻辑，我们可以编写如下的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=3
• mid = (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。这样，代码是正确的。可能我在刚才的分析中错误地修改了代码，但实际上代码是正确的。

所以，以上代码在所有示例中都能正确工作。