DEV Community
·
搜索-35. 搜索插入位置
💡
原文英文，约200词，阅读约需1分钟。
📝
内容提要
给定一个有序整数数组和目标值，找到目标则返回索引，否则返回插入位置索引。要求算法复杂度为O(log n)。例如：[1,3,5,6]中目标5返回2，目标2返回1，目标7返回4。
🎯
关键要点
-
给定一个有序整数数组和目标值，返回目标值的索引。
-
如果目标值不存在，返回插入位置的索引。
-
要求算法复杂度为O(log n)。
-
示例1：输入[1,3,5,6]，目标5，输出2。
-
示例2：输入[1,3,5,6]，目标2，输出1。
-
示例3：输入[1,3,5,6]，目标7，输出4。
-
代码实现使用循环遍历数组，检查目标值是否存在。
-
如果找到目标值，返回其索引；如果当前值大于目标值，返回当前索引作为插入位置。
-
如果遍历结束仍未找到目标值，返回数组长度作为插入位置。
❓
延伸问答
如何在有序数组中查找目标值的索引？
可以通过遍历数组，检查每个元素是否等于目标值，如果找到则返回该元素的索引。
如果目标值不存在，应该如何处理？
如果目标值不存在，返回它应该插入的位置索引，通常是当前元素大于目标值的索引。
这个算法的时间复杂度是多少？
该算法的时间复杂度为O(log n)。
能否给出一些示例来说明如何使用这个算法？
例如，对于数组[1,3,5,6]，目标值5返回索引2，目标值2返回索引1，目标值7返回索引4。
这个算法是如何实现的？
算法通过循环遍历数组，检查目标值是否存在，并在合适的位置返回索引。
在什么情况下返回数组的长度？
如果遍历结束仍未找到目标值，则返回数组的长度作为插入位置。
➡️
