搜索插入位置

题目要求

你需要解决的问题是在一个已排序的数组中查找一个目标值的索引位置。如果这个目标值在数组中存在，直接返回它的索引。如果不存在，需要返回这个目标值按照数组的排序规则应该被插入的位置。这个位置的确定是使得数组依然保持排序状态。

此外，题目要求你实现的算法必须具有 O(log n) 的时间复杂度，这意味着你不能使用简单的线性查找来遍历整个数组，因为线性查找的时间复杂度是 O(n)。相反，你应该考虑使用二分查找算法，因为二分查找的时间复杂度是 O(log n)，符合题目要求。

解题思路

由于数组是有序的，我们可以使用二分查找算法来优化搜索过程。二分查找算法的基本思想是，每次取中间位置的元素与目标值进行比较，根据比较结果缩小搜索范围，直到找到目标值或确定目标值不存在。

具体步骤如下：

初始化两个指针，一个指向数组的起始位置 left，另一个指向数组的结束位置 right。
在 left <= right 的条件下进行循环：
- 计算中间位置 mid = (left + right) / 2。
- 如果 mid 位置的元素等于目标值，直接返回 mid 作为答案。
- 如果 mid 位置的元素小于目标值，说明目标值应该在 mid 右侧的子数组中，因此将 left 更新为 mid + 1。
- 如果 mid 位置的元素大于目标值，说明目标值应该在 mid 左侧的子数组中，因此将 right 更新为 mid - 1。
如果循环结束后，没有找到目标值，此时 left 指针的位置就是目标值应该插入的位置。因为在二分查找的最后一步，如果目标值不存在，left 指针总是指向第一个大于目标值的元素位置，或者是数组的末尾（如果目标值比所有元素都大的情况）。

通过以上步骤，你可以在 O(log n) 的时间复杂度内找到目标值的索引或者应该插入的位置。

Golang 版本

package main

import "fmt"

func searchInsert(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return left
}

func main() {
    nums := []int{1, 3, 5, 6}
    target := 5
    fmt.Println("Index of target is:", searchInsert(nums, target))
}

这段代码实现了题目要求的功能，使用了二分查找算法来找到目标值的索引或者应该插入的位置。在 main 函数中，你可以通过更改 nums 和 target 的值来测试不同的情况。

C++版本

#include <iostream>
#include <vector>

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

int main() {
    std::vector<int> nums = {1, 3, 5, 6};
    int target = 5;
    std::cout << "Index of target is: " << searchInsert(nums, target) << std::endl;
    return 0;
}

这段 C++代码实现了与 Golang 版本相同的功能，使用二分查找算法来确定目标值的索引或者插入位置。在 main 函数中，可以通过修改 nums 和 target 的值来测试代码。

Python 版本

def search_insert(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 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 = 5
print("Index of target is:", search_insert(nums, target))

这段 Python 代码使用了二分查找算法来寻找目标值的索引或者插入位置。你可以通过更改 nums 和 target 的值来测试不同的输入情况。

Java 版本

public class SearchInsertPosition {
    public static int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 5, 6};
        int target = 5;
        System.out.println("Index of target is: " + searchInsert(nums, target));
    }
}

这段 Java 代码实现了题目要求的功能，使用二分查找算法来找到目标值的索引或者应该插入的位置。在 main 方法中，可以通过修改 nums 数组和 target 变量的值来测试不同的情况。

Rust 版本

fn search_insert(nums: Vec<i32>, target: i32) -> i32 {
    let (mut left, mut right) = (0, nums.len() as i32 - 1);
    while left <= right {
        let mid = left + (right - left) / 2;
        if nums[mid as usize] == target {
            return mid;
        } else if nums[mid as usize] < target {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    left
}

fn main() {
    let nums = vec![1, 3, 5, 6];
    let target = 5;
    println!("Index of target is: {}", search_insert(nums, target));
}

这段 Rust 代码实现了二分查找算法，用于在有序数组中查找目标值的索引或者目标值应该插入的位置。在 main 函数中，你可以通过更改 nums 向量和 target 的值来测试代码。

总结

上述解法都采用了二分查找算法来解决问题。二分查找是一种在有序数组中查找特定元素的高效算法，其时间复杂度为 O(log n)。算法的核心思想是将搜索区间分成两半，然后根据中间元素与目标值的比较结果来决定是继续在左侧区间搜索还是右侧区间搜索。

无论是 Golang、C++、Python 还是 Java 和 Rust 版本的代码，基本步骤如下：

初始化两个指针 left 和 right，分别指向数组的起始位置和结束位置。
在 left 小于等于 right 的条件下进行循环：
- 计算中间位置 mid。
- 如果 mid 位置的元素等于目标值，则返回 mid 作为索引。
- 如果 mid 位置的元素小于目标值，则将 left 更新为 mid + 1。
- 如果 mid 位置的元素大于目标值，则将 right 更新为 mid - 1。
如果循环结束还没有找到目标值，则 left 指针的位置表示目标值应该插入的位置。

这种方法不仅可以找到目标值的索引，如果目标值不存在于数组中，还能找到它按顺序应该被插入的位置。

hot-100