题目描述

给定一个已排序的数组和一个目标值，在数组中找到一个可以插入该目标值以保持数组排序的索引位置。如果数组中存在多个相同的值，则插入后应该保持它们的相对顺序。你可以假设数组中不存在重复的元素（为了简化问题，但在示例中我们将展示如何处理）。

返回目标值应该插入的位置的索引。如果目标值已经存在于数组中，则返回它的索引。

示例

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

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

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

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

PHP 示例代码

function searchInsert($nums, $target) {
    $left = 0;
    $right = count($nums) - 1;
    
    while ($left <= $right) {
        $mid = $left + floor(($right - $left) / 2);
        
        if ($nums[$mid] == $target) {
            return $mid;
        } elseif ($nums[$mid] < $target) {
            $left = $mid + 1;
        } else {
            $right = $mid - 1;
        }
    }
    
    return $left;
}

// 示例
$nums = [1, 3, 5, 6];
$target = 2;
echo searchInsert($nums, $target); // 输出: 1

Python 示例代码

def searchInsert(nums, target):
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return left

# 示例
nums = [1, 3, 5, 6]
target = 2
print(searchInsert(nums, target))  # 输出: 1

JavaScript 示例代码

function searchInsert(nums, target) {
    let left = 0;
    let right = nums.length - 1;
    
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        
        if (nums[mid] === target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return left;
}

// 示例
const nums = [1, 3, 5, 6];
const target = 2;
console.log(searchInsert(nums, target)); // 输出: 1

在这些示例中，我们使用二分查找的思想来高效地找到或确定目标值应该插入的位置。通过维护一个搜索区间，并不断更新左右边界，我们能够以接近 O(log n) 的时间复杂度来解决问题。在达到区间无效（即左边界大于右边界）时，我们返回左边界，这表示了目标值应该插入的位置。