07.01_二分查找
二分查找
问题描述
在一个有序数组中查找目标值的位置。根据需求可以返回第一个大于等于目标值的位置（lower_bound）或第一个大于目标值的位置（upper_bound）。
lower_bound
算法思想
- 查找第一个大于等于目标值的位置
- 使用左闭右开区间 [left, right)
- 如果找不到，返回数组长度
- 时间复杂度
代码实现
class Solution {
public:
int lower_bound(vector<int>& nums, int target) {
int left = 0, right = nums.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
};
class Solution {
public int lower_bound(int[] nums, int target) {
int left = 0, right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
class Solution:
def lower_bound(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums)
while left < right:
mid = left + (right - left) // 2
if nums[mid] >= target:
right = mid
else:
left = mid + 1
return left
upper_bound
算法思想
- 查找第一个大于目标值的位置
- 使用左闭右开区间 [left, right)
- 如果找不到，返回数组长度
- 时间复杂度
代码实现
class Solution {
public:
int upper_bound(vector<int>& nums, int target) {
int left = 0, right = nums.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > target) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
};
class Solution {
public int upper_bound(int[] nums, int target) {
int left = 0, right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > target) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
class Solution:
def upper_bound(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums)
while left < right:
mid = left + (right - left) // 2
if nums[mid] > target:
right = mid
else:
left = mid + 1
return left
时间复杂度分析
| lower_bound | ||
| upper_bound |
应用场景
- 有序数组查找
- 边界值确定
- 旋转数组查找
- 插入位置查找
- 范围查询
注意事项
- 区间表示方式（左闭右开）
- 中点计算的溢出
- 循环条件的选择
- 返回值的含义
- 空数组的处理
常见变形
- 查找目标值的任意位置
int binarySearch(vector<int>& nums, int target) {
int pos = lower_bound(nums, target);
if (pos < nums.size() && nums[pos] == target) {
return pos;
}
return -1;
}
class Solution {
public int binarySearch(int[] nums, int target) {
int pos = lower_bound(nums, target);
if (pos < nums.length && nums[pos] == target) {
return pos;
}
return -1;
}
}
class Solution:
def binarySearch(self, nums: List[int], target: int) -> int:
pos = self.lower_bound(nums, target)
if pos < len(nums) and nums[pos] == target:
return pos
return -1
- 查找目标值的范围
vector<int> searchRange(vector<int>& nums, int target) {
int left = lower_bound(nums, target);
int right = lower_bound(nums, target + 1);
if (left < nums.size() && nums[left] == target) {
return {left, right - 1};
}
return {-1, -1};
}
class Solution {
public int[] searchRange(int[] nums, int target) {
int left = lower_bound(nums, target);
int right = lower_bound(nums, target + 1);
if (left < nums.length && nums[left] == target) {
return new int[]{left, right - 1};
}
return new int[]{-1, -1};
}
}
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
left = self.lower_bound(nums, target)
right = self.lower_bound(nums, target + 1)
if left < len(nums) and nums[left] == target:
return [left, right - 1]
return [-1, -1]
牛客代码笔记-牛栋 文章被收录于专栏
汗牛充栋，学海无涯。<br/> 内含算法知识点讲解，以及牛客题库精选例题。<br/> 学习算法，从牛栋开始。
投递神州信息等公司10个岗位 >