力扣“找出数组排序后的目标下标”：一种简洁高效的算法

**力扣 "找出数组排序后的目标下标"**

在力扣中，经常会遇到一个问题：给定一个未排序的数组和一个目标值，我们需要找到这个目标值在排序后数组中的下标。这种问题看似简单，但实际上涉及到一些复杂的算法设计。

**传统解决方案**

最直接的解决方案是先对数组进行排序，然后再使用二分查找（Binary Search）来找到目标值的下标。但是，这种方法有一个明显的缺点：时间复杂度为 O(n log n)，其中 n 是数组长度。这对于大型数据集来说是不合适的。

**一种简洁高效的算法**

我们可以使用一种更高效的算法来解决这个问题。这种算法基于以下观察：

* 如果目标值小于或等于中间元素，则目标值一定在前半段。
* 如果目标值大于中间元素，则目标值一定在后半段。

通过反复使用这种观察，我们可以将数组分成两半，直到找到目标值的下标。这种算法称为二叉查找（Binary Search）。

**代码实现**

def searchInsert(nums, target):
 """
 在未排序的数组中找到目标值的下标。

 Args:
 nums (list): 未排序的数组。
 target (int): 目标值。

 Returns:
 int: 目标值在排序后数组中的下标。
 """

 # 初始化左边界和右边界 left, right =0, len(nums) -1 # 反复使用二叉查找算法直到找到目标值的下标 while left <= right:
 mid = (left + right) //2 # 如果目标值等于中间元素，则返回下标 if nums[mid] == target:
 return mid # 如果目标值小于中间元素，则移动右边界 elif nums[mid] > target:
 right = mid -1 # 如果目标值大于中间元素，则移动左边界 else:
 left = mid +1 # 如果目标值不在数组中，则返回左边界（即下标）
 return left# 示例用法nums = [1,3,5,6]
target =5print(searchInsert(nums, target)) # 输出：2nums = [1,3,5,6]
target =2print(searchInsert(nums, target)) # 输出：1nums = [1,3,5,6]
target =7print(searchInsert(nums, target)) # 输出：4