35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。
示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

来源：力扣（LeetCode）
链接：https:///problems/search-insert-position

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left=0;
        int right=nums.size()-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(nums[mid]>target){
                right=mid-1;
            }else if(nums[mid]<target){
                left=mid+1;
            }else{
                return mid;
            }
        }
        return left;
    }
};

这段代码是一个名为Solution的类，其中包含一个名为searchInsert的成员函数。该函数接受一个整数数组nums和一个目标整数target作为输入，并返回一个整数值。

函数的主要目的是在给定的排序数组nums中查找目标值target的索引位置。如果目标值存在于数组中，则返回目标值的索引。如果目标值不存在于数组中，函数将返回插入目标值后的索引位置，以保持数组的有序性。

代码使用二分查找算法来搜索目标值。它使用两个指针left和right来跟踪搜索的范围。初始时，left指向数组的起始位置，right指向数组的末尾位置。

在循环中，首先计算中间索引mid，这样可以将搜索范围缩小一半。然后，检查中间元素nums[mid]与目标值target之间的关系。

• 如果nums[mid]大于target，说明目标值应该在mid的左侧，因此将right更新为mid-1，将搜索范围缩小到左半部分。
• 如果nums[mid]小于target，说明目标值应该在mid的右侧，因此将left更新为mid+1，将搜索范围缩小到右半部分。
• 如果nums[mid]等于target，说明找到了目标值，直接返回mid作为结果。

循环继续，直到left大于right，表示搜索范围为空，即目标值不存在于数组中。此时，返回left作为插入目标值后的索引位置。

总结起来，该函数使用二分查找算法，在排序数组中查找目标值的索引位置，或者返回插入目标值后的索引位置。