【算法拾光】二分查找｜二分查找 + 再排序数组中查找元素的第一个和最后一个位置

标签：二分查找、左边界二分、右边界二分、LeetCode 704 / LeetCode 34 区间规范：统一使用 左闭右闭 [left, right] 写法，工程、面试最稳，减少边界 bug

一、LeetCode 704 二分查找704. 二分查找 – 力扣（LeetCode）

1. 题目分析

题目：给定一个升序排列、无重复元素的整型数组 nums 和目标值 target。如果数组中存在目标值，返回它的下标；不存在则返回 -1。 已知条件：数组有序、元素不重复 需求：快速定位目标，不暴力遍历 暴力缺点：O (n)，数据量大时很慢；二分可以做到 O (log n)

2. 算法原理（分步）

二分核心思想：有序数组可以不断折半，排除一半不可能的区间

3. 代码编写

class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() – 1;
while(left <= right){
int mid = left + (right – left) / 2;
if(nums[mid] == target){
return mid;
}else if(nums[mid] < target){
left = mid + 1;
}else{
right = mid – 1;
}
}
return -1;
}
};

二、LeetCode 34 在排序数组中查找元素的第一个和最后一个位置34. 在排序数组中查找元素的第一个和最后一个位置 – 力扣（LeetCode）

1. 题目分析

题目：升序整型数组（允许元素重复），给目标值 target，找出目标在数组里第一次出现的下标 和 最后一次出现的下标；不存在返回 [-1, -1] 难点：数组有重复！普通二分找到一个就退出，无法拿到左右边界。 举例：nums = [5,7,7,8,8,10], target=8，答案是 [3,4] 需求拆解：

• 子问题 1：二分找左边界：等于 target 的最靠左位置
• 子问题 2：二分找右边界：等于 target 的最靠右位置

2. 算法原理（分步）

依然使用左闭右闭 [left, right]，和 704 保持一套逻辑，方便记忆

找左边界逻辑

找右边界逻辑

主函数逻辑

分别调用获取左边界、右边界两个函数，组装成 vector 返回。

3. 代码编写

class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int leftBound = getLeftBound(nums, target);
int rightBound = getRightBound(nums, target);
return {leftBound, rightBound};
}

// 获取左边界：第一个等于target的下标
int getLeftBound(vector<int>& nums, int target){
int left = 0;
int right = nums.size() – 1;
int res = -1;
while(left <= right){
int mid = left + (right – left) / 2;
if(nums[mid] == target){
res = mid;
right = mid – 1;
}else if(nums[mid] < target){
left = mid + 1;
}else{
right = mid – 1;
}
}
return res;
}

// 获取右边界：最后一个等于target的下标
int getRightBound(vector<int>& nums, int target){
int left = 0;
int right = nums.size() – 1;
int res = -1;
while(left <= right){
int mid = left + (right – left) / 2;
if(nums[mid] == target){
res = mid;
left = mid + 1;
}else if(nums[mid] < target){
left = mid + 1;
}else{
right = mid – 1;
}
}
return res;
}
};

三、两篇对比总结

表格

核心口诀：有序才能二分；普通二分找到就走，边界二分找到不松手，往一边挤！