行业知识
备战蓝桥杯————二分查找(二)
引言
�� 在上一篇博客中,我们深入探讨了二分搜索算法及其在寻找数组左侧边界的应用。二分搜索作为一种高效的查找方法,其核心思想在于通过不断缩小搜索范围来定位目标值。在本文中,我们将继续这一主题,不仅会回顾二分搜索的基本原理,还将重点介绍如何利用这一算法来寻找数组中目标值的右侧边界。通过对比左侧和右侧边界的搜索,我们将揭示二分搜索算法的灵活性和强大功能。无论您是在准备技术面试,还是在日常编程中寻求效率提升,本文都将为您提供宝贵的洞见。
一、寻找右侧边界的二分查找
在有序数组中寻找特定值的右侧边界是二分查找算法的一个重要变体。与寻找左侧边界类似,我们可以通过调整搜索区间的边界来实现。本文将介绍两种写法:左闭右开的常见写法和两端都闭的统一写法。
基本代码
int right_bound(int[] nums, int target) { int left = 0, right = nums.length; while (left target) { right = mid; } } return left - 1; // 注意} 代码解释
1. 为什么这个算法能够找到右侧边界?
答:关键在于当 nums[mid] == target 时,我们不立即返回,而是通过 left = mid + 1 增大搜索区间的左边界,从而锁定右侧边界。
2. 为什么最后返回 left - 1 而不是 left?
答:由于循环终止时 left 和 right 相等,而我们希望返回的是目标值的右侧边界,所以需要返回 left - 1。这样,当 left 等于数组长度时,表示目标值不存在,返回 -1。
3. 如何处理目标值不存在的情况?
答:在循环结束后,我们检查 nums[left - 1] 是否等于目标值。如果不等于,或者 left - 1 索引越界,说明目标值不存在,返回 -1。
二、在排序数组中查找元素的第一个跟最后一个
题目描述
给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target,返回 [-1, -1]。你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 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]
提示:
- 0
上一篇:河南少林寺服务器怎么样?