set的二分查找的返回值

时间: 2024-06-18 15:04:30 浏览: 108

二分查找

### 二分查找知识点详解 #### 一、二分查找基本概念二分查找（Binary Search），也称为折半查找，是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是目标值，则搜索结束；如果目标值大于或小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。 #### 二、二分查找的时间复杂度与空间复杂度 1. **时间复杂度**：最坏情况下的时间复杂度为 O(log n)，其中 n 是数组中的元素数量。这是因为每次比较后，搜索区间都会减半。 2. **空间复杂度**：二分查找的空间复杂度为 O(1)。这是因为它只需要几个额外的变量来保存起始位置、结束位置等信息，而这些变量的数量不随输入数据规模的变化而变化。 #### 三、二分查找的应用场景 1. **有序数组的查找**：二分查找适用于已排序的数组或列表，如数据库索引的快速检索、搜索引擎结果的优化等。 2. **近似匹配问题**：在某些情况下，需要找到最接近某个值的元素时，可以使用二分查找。 3. **数值分析**：在解决某些数学问题时，可以通过二分查找逼近问题的解。 #### 四、二分查找的实现细节根据给定的部分代码，我们可以看到一个不完整的二分查找实现示例。下面将对该代码进行解析，并提供一个更完整的二分查找实现。 ```csharp using System; class Test { static void Main() { string[] str = { "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K" }; bool stop = false; int s, e; s = 0; e = str.Length - 1; // 应该是数组长度减1，而非除以2 while (!stop && s <= e) { int result = a(ref s, ref e, str); if (result != -1) { Console.WriteLine("Element found at index: " + result); stop = true; } } if (!stop) { Console.WriteLine("Element not found."); } } private static int a(ref int s, ref int e, string[] str) { string search = "G"; int mid = (s + e) / 2; if (str[mid] == search) { return mid; } else if (str[mid].CompareTo(search) < 0) { s = mid + 1; return -1; } else { e = mid - 1; return -1; } } } ``` #### 五、二分查找的关键点解析 1. **初始化指针**：`s` 和 `e` 分别表示搜索区间的开始和结束位置。在初始化时，`s` 设置为 0，`e` 设置为数组的最后一个元素的下标。 2. **计算中间位置**：中间位置 `mid` 通过 `(s + e) / 2` 计算得到。这里需要注意，当数组长度为奇数时，中间位置会取较大的一个。 3. **递归或迭代**：二分查找可以通过递归或迭代的方式实现。上述代码使用了迭代方式。 4. **退出条件**：当 `s > e` 时，表示搜索区间为空，即没有找到目标值。 5. **处理边界条件**：对于边界条件的处理非常重要，例如在查找过程中可能会出现 `s` 或 `e` 的更新使得它们超出数组的有效范围，此时需要特别注意。 #### 六、二分查找的变种除了标准的二分查找之外，还有一些变种形式： 1. **左边界查找**：查找第一个等于给定值的元素。 2. **右边界查找**：查找最后一个等于给定值的元素。 3. **查找范围**：返回给定值出现的第一个位置和最后一个位置。 4. **最接近值查找**：查找离给定值最近的元素。二分查找是一种高效的查找方法，广泛应用于计算机科学的多个领域。理解和掌握其基本原理及实现细节，对于提高编程能力具有重要意义。

set的二分查找返回一个迭代器，指向当前查找元素的位置。如果元素存在，迭代器指向该元素；如果元素不存在，则迭代器指向第一个大于该元素的元素。你可以使用lower_bound和upper_bound函数来进行二分查找。lower_bound函数返回第一个大于等于给定值的元素的迭代器，而upper_bound函数返回第一个大于给定值的元素的迭代器。

阅读全文

set的二分查找的返回值

相关推荐

二分查找

全国计算机等级考试二级python第二套试卷

Python核心编程第二版

2010年二级c语言考试试题

java代码-笔试第二题

二级C++学习资料包历年真题

疯狂Python讲义第二章课后习题

C++ unordered_set与STL算法

【集合的自定义实现】：深入理解集合背后的数据结构，打造个性化的Set类

关联数组算法应用：查找、排序和聚合的利器

【哈希表：揭秘数据结构中的快速查找利器】

【实战演练】：打造高效自定义查找算法库的步骤与案例

【Python数据结构优化技巧】：5个提升列表查找速度的方法

find_in_set

mysql FIND_IN_SET

find_in_set()函数

find_in_set多条件查询优化

请编写函数，判断一个集合是另一个集合的子集。 A⊆B⟺(∀ x)(x∈A→x∈B) 函数原型 int ASetLe(const ASET *set1, const ASET *set2);

最新推荐

python使用threading获取线程函数返回值的实现方法

Sql Server 存储过程调用存储过程接收输出参数返回值

mysql存储过程 在动态SQL内获取返回值的方法详解

Python中执行存储过程及获取存储过程返回值的方法

java中set接口使用方法详解

C语言数组操作：高度检查器编程实践

管理建模和仿真的文件

【KUKA系统变量进阶】：揭秘从理论到实践的5大关键技巧

如何使用Python编程语言创建一个具有动态爱心图案作为背景并添加文字'天天开心（高级版）'的图形界面？

基于Swift开发的嘉定单车LBS iOS应用项目解析

二分查找　

请编写函数，判断一个集合是另一个集合的子集。 A⊆B⟺(∀ x)(x∈A→x∈B) 函数原型 int ASetLe(const ASET set1, const ASET set2);

mysql存储过程在动态SQL内获取返回值的方法详解