找到最接近目标值的搜索算法

题目描述：给定一个已排序的整数数组和一个目标值，如果目标值存在于数组中，则返回其索引；如果不存在，则返回其应该被插入的位置，使得数组仍然有序。此外，你需要确保算法的时间复杂度为 O(log n)。

解题过程：

1. 这个问题是二分查找的一个变种，关键在于处理目标值不存在于数组中的情况。我们需要找到第一个大于或等于目标值的元素位置。

2. 初始化两个指针：left 指向数组起始位置（索引 0），right 指向数组末尾（索引 n-1）。

3. 在 left <= right 的条件下循环：

   • 计算中间位置 mid = left + (right - left) / 2（防止整数溢出）。
   • 如果 nums[mid] 等于目标值，直接返回 mid。
   • 如果 nums[mid] 小于目标值，说明目标值在右半部分，将 left 设为 mid + 1。
   • 如果 nums[mid] 大于目标值，说明目标值在左半部分，将 right 设为 mid - 1。

4. 循环结束后，left 指针指向的位置就是目标值应该插入的位置。因为当目标值不存在时，left 会停在第一个大于目标值的元素位置，或者数组末尾（如果目标值大于所有元素）。

5. 举例说明：数组 [1,3,5,6]，目标值 2。

   • 第一次循环：left=0, right=3, mid=1 → nums[1]=3 > 2 → right=0
   • 第二次循环：left=0, right=0, mid=0 → nums[0]=1 < 2 → left=1
   • 循环结束，left=1 正是插入位置（在 1 和 3 之间插入 2）。

6. 这个算法保证了 O(log n) 的时间复杂度，因为每次循环都将搜索范围减半。