【算法面试】在排序数组中查找元素的第一个和最后一个位置：详细题解

目录

题目描述

示例

示例 1：

示例 2：

示例 3：

问题分析

详细步骤

解决方法

方法 1：标准二分查找（分开查找第一个和最后一个）

方法 2：优化版二分查找（合并查找逻辑）

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

总结

博主v：XiaoMing_Java

---

题目描述

在处理有序数组时，一个常见的问题是查找特定元素的起始和结束位置。给定一个按照非递减顺序排列的整数数组 nums 和一个目标值 target，我们需要找到目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。

示例

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8

输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6

输出：[-1,-1]

示例 3：

输入：nums = [], target = 0

输出：[-1,-1]

问题分析

由于数组是有序的，因此可以利用二分查找的方法来高效地解决这个问题。二分查找的时间复杂度为 O(log n)，非常适合查找任务。

为了找到目标值的起始和结束位置，我们可以分别使用两次二分查找：

1. 第一次查找目标值的起始位置。
2. 第二次查找目标值的结束位置。

详细步骤

1. 初始化：设置 left 为数组的起始索引 0，right 为数组的末尾索引 n-1。
2. 查找起始位置：
   • 使用二分查找，如果找到目标值，则继续向左半部分查找，直到找到最左边的目标值。
3. 查找结束位置：
   • 使用二分查找，如果找到目标值，则继续向右半部分查找，直到找到最右边的目标值。
4. 组合结果：返回找到的起始位置和结束位置。

解决方法

方法 1：标准二分查找（分开查找第一个和最后一个）

以下是实现二分查找的一种标准方法，通过两次二分查找分别查找第一个和最后一个目标值的位置：

// 两次二分查找，分开查找第一个和最后一个
// 时间复杂度 O(log n), 空间复杂度 O(1)
// [1,2,3,3,3,3,4,5,9]
public int[] searchRange2(int[] nums, int target) {
	int left = 0;
	int right = nums.length - 1;
	int first = -1;
	int last = -1;
	// 找第一个等于target的位置
	while (left <= right) {
		int middle = (left + right) / 2;
		if (nums[middle] == target) {
			first = middle;
			right = middle - 1; // 重点
		} else if (nums[middle] > target) {
			right = middle - 1;
		} else {
			left = middle + 1;
		}
	}
	// 最后一个等于target的位置
	left = 0;
	right = nums.length - 1;
	while (left <= right) {
		int middle = (left + right) / 2;
		if (nums[middle] == target) {
			last = middle;
			left = middle + 1; // 重点
		} else if (nums[middle] > target) {
			right = middle - 1;
		} else {
			left = middle + 1;
		}
	}
	return new int[] { first, last };
}

方法 2：优化版二分查找（合并查找逻辑）

为了代码更简洁，可以将查找最左和最右位置的逻辑合并到一个函数中，并通过传递额外参数来控制查找方向：

public int[] searchRange(int[] nums, int target) {
    int first = findBound(nums, target, true);
    int last = findBound(nums, target, false);
    return new int[] { first, last };
}
 
private int findBound(int[] nums, int target, boolean isFirst) {
    int left = 0;
    int right = nums.length - 1;
    int bound = -1;
 
    while (left <= right) {
        int middle = left + (right - left) / 2;
        if (nums[middle] == target) {
            bound = middle;
            if (isFirst) {
                right = middle - 1; // 查找最左位置
            } else {
                left = middle + 1; // 查找最右位置
            }
        } else if (nums[middle] > target) {
            right = middle - 1;
        } else {
            left = middle + 1;
        }
    }
 
    return bound;
}

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

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

public int[] searchRange(int[] nums, int target) {
    int first = findBound(nums, target, true);
    int last = findBound(nums, target, false);
    return new int[] { first, last };
}
 
private int findBound(int[] nums, int target, boolean isFirst) {
    int left = 0;
    int right = nums.length - 1;
    int bound = -1;
 
    while (left <= right) {
        int middle = left + (right - left) / 2;
        System.out.println("Left: " + left + ", Mid: " + middle + ", Right: " + right);
 
        if (nums[middle] == target) {
            bound = middle;
            if (isFirst) {
                right = middle - 1; // 查找最左位置
            } else {
                left = middle + 1; // 查找最右位置
            }
        } else if (nums[middle] > target) {
            right = middle - 1;
        } else {
            left = middle + 1;
        }
    }
 
    System.out.println(isFirst ? "First bound found at: " + bound : "Last bound found at: " + bound);
    return bound;
}

总结

通过使用二分查找的方式，我们可以在 O(log n) 的时间复杂度内高效地找到排序数组中目标值的起始和结束位置。本文展示了多种实现方法，包括标准二分查找、优化版二分查找以及带调试信息的版本，以帮助读者更好地理解并应用这种算法。希望这些方法能够帮助你解决实际开发中的问题，确保程序顺利运行。

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

博主v：XiaoMing_Java

 📫作者简介：嗨，大家好，我是 小 明（小明java问道之路），互联网大厂后端研发专家，2022博客之星TOP3 / 博客专家 / CSDN后端内容合伙人、InfoQ(极客时间)签约作者、阿里云签约博主、全网5万粉丝博主。

---

🍅 文末获取联系 🍅  👇🏻 精彩专栏推荐订阅收藏 👇🏻

专栏系列（点击解锁）	学习路线（点击解锁）	知识定位
🔥Redis从入门到精通与实战🔥	Redis从入门到精通与实战	围绕原理源码讲解Redis面试知识点与实战
🔥MySQL从入门到精通🔥	MySQL从入门到精通	全面讲解MySQL知识与企业级MySQL实战
🔥计算机底层原理🔥	深入理解计算机系统CSAPP	以深入理解计算机系统为基石，构件计算机体系和计算机思维
	Linux内核源码解析	围绕Linux内核讲解计算机底层原理与并发
🔥数据结构与企业题库精讲🔥	数据结构与企业题库精讲	结合工作经验深入浅出，适合各层次，笔试面试算法题精讲
🔥互联网架构分析与实战🔥	企业系统架构分析实践与落地	行业最前沿视角，专注于技术架构升级路线、架构实践
	互联网企业防资损实践	互联网金融公司的防资损方法论、代码与实践
🔥Java全栈白宝书🔥	精通Java8与函数式编程	本专栏以实战为基础，逐步深入Java8以及未来的编程模式
	深入理解JVM	详细介绍内存区域、字节码、方法底层，类加载和GC等知识
	深入理解高并发编程	深入Liunx内核、汇编、C++全方位理解并发编程
	Spring源码分析	Spring核心七IOC/AOP等源码分析
	MyBatis源码分析	MyBatis核心源码分析
	Java核心技术	只讲Java核心技术