搜索插入位置

题解思路

本题要求在一个 有序数组 中找到目标值的索引，或者确定它应该插入的位置。由于数组已经是 升序排列，我们可以使用 二分查找算法（Binary Search），该算法的时间复杂度为 O(log n)，满足题目要求。

二分查找方法：

1. 设定左右指针 left 和 right，初始值分别为 0 和 n-1。
2. 进行 循环查找，直到 left 超过 right：
   • 计算中间索引 mid = (left + right) // 2。

Leetcode 63.搜索插入位置-原题链接

题目内容

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

请必须使用时间复杂度为 $0(log\ n)$的算法。

输入描述

• 第一行：两个整数，第一个整数表示数组的长度 $n$，第二个整数表示目标值 $target$。
• 第二行：包含 $n$ 个整数的数组 $nums$，数组中的元素按升序排列，且无重复元素。

输出描述

一个整数，表示目标值 $target$ 在数组 $nums$ 中的索引。如果 $target$ 不存在于数组中，则输出它应该被插入的位置。

样例1

输入

4 5
1 3 5 6

输出

2

样例2

输入

4 2
1 3 5 6

输出

1

样例3

输入

4 7
1 3 5 6

输出

4

提示

• $1 <= nums.length <= 10^4$
• $-10^4 <= nums[i] <= 10^4$
• $nums$为 无重复元素 的 升序 排列数组
• $-10^4 <= target <= 10^4$