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

在处理有序数组时，我们经常会遇到这样一个问题：给定一个排序数组和一个目标值，需要找到目标值在数组中的索引。如果目标值不存在于数组中，则返回它将会被按顺序插入的位置。为了提高效率，我们需要使用时间复杂度为 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 <= right) { // 等于0是为了防止 [1,3,5,6] 0 的case
		int mid = (left + right) / 2;
		if (target <= nums[mid]) {
			l = mid;
			right = mid - 1;
		} else {
			left = mid + 1;
		}
	}
	return l;
}

方便理解的版本： 

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

方法 2：递归二分查找

我们还可以采用递归方式实现搜索插入位置：

public int searchInsert(int[] nums, int target) {
    return binarySearch(nums, target, 0, nums.length - 1);
}
 
private int binarySearch(int[] nums, int target, int left, int right) {
    if (left > right) {
        return left;
    }
    
    int mid = left + (right - left) / 2; // 防止溢出
    
    if (nums[mid] == target) {
        return mid;
    } else if (nums[mid] < target) {
        return binarySearch(nums, target, mid + 1, right);
    } else {
        return binarySearch(nums, target, left, mid - 1);
    }
}

方法 3：带调试信息的版本

为了更好地理解算法，可以添加调试信息来跟踪程序执行过程：

public int searchInsert(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        System.out.println("Left: " + left + ", Mid: " + mid + ", Right: " + right);
 
        if (nums[mid] == target) {
            System.out.println("Found target at index: " + mid);
            return mid;
        }
        
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    System.out.println("Target not found, insert position: " + left);
    return left;
}

详细步骤

1. 初始化：设置 left 为数组的起始索引 0，right 为数组的末尾索引 n-1。
2. 计算中点：在每个迭代中，计算中点 mid 的索引，避免直接加和可能导致的溢出。
3. 比较中点值：将中点值与目标值 target 比较：
   • 若相等，返回中点索引。
   • 若中点值大于目标值，将 right 更新为 mid - 1。
   • 若中点值小于目标值，将 left 更新为 mid + 1。
4. 重复操作：继续上述步骤直到 left 超过 right，表示目标值不在数组中，返回 left。

总结

搜索插入位置的问题非常适合使用二分查找算法，因为其时间复杂度为 O(log n)，能够在大规模有序数组中高效地查找目标值的索引或插入位置。本文展示了多种实现方法，包括标准二分查找、递归二分查找以及带调试信息的版本，以帮助读者更好地理解并应用这种算法。希望这些方法能够帮助你解决实际开发中的问题，确保程序顺利运行。

 如果本文对你有帮助 欢迎 关注、点赞、收藏、评论！！！

博主v：XiaoMing_Java

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/正经夜光杯/article/detail/766207