【算法面试】搜索插入位置：如何在排序数组中高效查找目标值的索引或插入位置

在处理有序数组时，我们经常会遇到这样一个问题：给定一个排序数组和一个目标值，需要找到目标值在数组中的索引。如果目标值不存在于数组中，则返回它将会被按顺序插入的位置。为了提高效率，我们需要使用时间复杂度为 O(log n) 的算法，这意味着二分查找是一个理想的选择。

题目描述

假设你有一个包含 n 个元素的升序整型数组 nums，以及一个目标值 target。你需要编写一个函数，在数组 nums 中查找 target 的索引，如果目标值存在则返回其索引；如果目标值不存在，则返回它将要被插入的位置。

示例 1:

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

输出: 2

示例 2:

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

输出: 1

示例 3:

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

输出: 4

问题分析

为了实现这一功能，我们可以采用二分查找算法。二分查找的核心思想是通过不断将查找范围对半划分，从而迅速缩小查找范围。这种方法适用于在有序数组中进行查找操作，并且时间复杂度为 O(log n)。

解决方法

方法 1：标准二分查找

以下是实现搜索插入位置的一种标准方法：

public int searchInsert(int[] nums, int target) {
	int left = 0, right = nums.length - 1, l = nums.length;
	while (left