温州开发网站公司,青岛天河小学网站建设,大型软件公司有哪些,物联网学什么二分查找是一种经典的搜索算法#xff0c;广泛应用于有序数据集中。它允许在大型数据集中高效地查找目标元素#xff0c;减少了搜索的时间复杂度。本文将介绍在 C 和 Python 中内置的二分查找函数#xff0c;让二分查找变得更加容易。
c
lower_bound() 、upper_bound
定义…二分查找是一种经典的搜索算法广泛应用于有序数据集中。它允许在大型数据集中高效地查找目标元素减少了搜索的时间复杂度。本文将介绍在 C 和 Python 中内置的二分查找函数让二分查找变得更加容易。
c
lower_bound() 、upper_bound
定义在algorithm头文件中, lower_bound 和 upper_bound 是 C STL 中与二分查找相关的两个非常有用的函数。它们都用于在有序容器中查找元素的位置。下面我将通过一个示例来详细讲解它们的用法。
假设我们有一个有序的整数数组 arr如下所示
#include iostream
#include vector
#include algorithmint main() {std::vectorint arr {1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 8, 9};int target 4;// 使用 lower_bound 查找目标值的第一个出现位置std::vectorint::iterator lower std::lower_bound(arr.begin(), arr.end(), target);// 使用 upper_bound 查找目标值的最后一个出现位置的下一个位置std::vectorint::iterator upper std::upper_bound(arr.begin(), arr.end(), target);// 输出结果std::cout 数组中 target 的出现位置 std::endl;std::cout lower_bound 的结果 std::distance(arr.begin(), lower) std::endl;std::cout upper_bound 的结果 std::distance(arr.begin(), upper) std::endl;return 0;
}
在上述示例中我们使用了 lower_bound 和 upper_bound 函数来查找目标值 4 在数组中的位置。下面是这两个函数的详细解释 lower_bound它返回一个迭代器指向数组中第一个不小于目标值的元素。在我们的示例中lower 将指向数组中第一个 4 的位置。 upper_bound它返回一个迭代器指向数组中第一个大于目标值的元素。在我们的示例中upper 将指向数组中第一个大于 4 的元素位置。
请注意如果目标值在数组中不存在lower 和 upper 的差值将为零因为它们将指向同一个位置。这两个函数在查找有序容器中的范围时非常有用帮助我们精确定位元素的位置。
python
bisect_left
bisect.bisect_left(a, x, lo0, hilen(a), *, keyNone) bisect.bisect_left 函数在 Python 的 bisect 模块中用于在有序序列中查找目标值的插入位置它接受四个参数 a表示有序序列通常是一个列表。 x表示要查找的目标值。 lo可选表示搜索范围的起始位置默认为 0。 hi可选表示搜索范围的结束位置默认为序列的长度。 下面是一个示例演示了 bisect.bisect_left 函数的用法
import bisectarr [1, 2, 3, 4, 4, 4, 5, 6, 7, 8, 9]
target 4# 在整个序列中查找目标值的插入位置
index bisect.bisect_left(arr, target)
print(f在整个序列中查找 {target} 的插入位置{index})# 在指定范围内查找目标值的插入位置
lo 2 # 搜索范围的起始位置
hi 7 # 搜索范围的结束位置
index_range bisect.bisect_left(arr, target, lo, hi)
print(f在范围 [{lo}, {hi}] 内查找 {target} 的插入位置{index_range})
在上述示例中首先我们在整个序列中查找目标值 4 的插入位置然后在指定范围 [2, 7] 内查找 4 的插入位置。这两个插入位置的结果将告诉你如果将目标值插入到序列中它应该出现在哪个位置。
bisect_right
bisect.bisect_right 函数与 bisect.bisect_left 函数非常类似都用于在有序序列中查找目标值的插入位置。它们的区别在于bisect_right 返回的位置是目标值插入后应该位于的右侧位置而 bisect_left 返回的位置是目标值插入后应该位于的左侧位置。
