一只猪

用户名：TuT99

访问量：12303

签　名：

拥有良好的积累，并且一直在路上，我相信自己有无限的可能

等　　级
排　　名	70
经　　验	10322
参赛次数	6
文章发表	68
年　　龄	21
在职情况	学生
学　　校	哔哩哔哩大学
专　　业	计算机科学与技术

　　自我简介：

TA的其他文章

简单又实用
浏览：185

简单又实用
浏览：49

简单又实用
浏览：138

你可能喜欢

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

C++常用算法和数据结构（STL）

　　作者: 一只猪　　　　发表时间：2023-06-24 20:54:37 浏览：44　|　评论：0　

## 主要是分享，其次是偷懒
2 查找算法
2.1二分查找
原理：
二分查找（Binary Search）是一种非常基础和常用的查找算法，它的主要使用场景是在有序数组中查找目标值。二分查找的基本原理可以概括为：
1、将有序数组的中间位置记为mid；
2、比较mid位置的值和目标值的大小，若mid位置上的值等于目标值，则查找结束；
3、若mid位置上的值小于目标值，则将待查找范围缩小到右半部分的子数组；
4、若mid位置上的值大于目标值，则将待查找范围缩小到左半部分的子数组；
5、继续执行第一步，直到找到目标元素或待查找的子数组为空。
缺点：
1、必须在有序数组上进行查找；
2、数组的插入、删除比较困难，因为插入和删除意味着整个数组的重新排序；
3、时间复杂度虽然很低，但是针对某些特定的数据，在实现二分查找时仍然容易出现问题。
优点：
1、时间复杂度较低，这是二分查找的最大优点；
2、空间复杂度较低，只需要少量辅助变量即可实现；
3、查找效率稳定，不受查找数值的影响。
复杂度：
空间复杂度为O(1)
时间复杂度为O(logn)
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool binarySearch(const vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;

while (left <= right) {
        int mid = left + (right - left) / 2;

if (arr[mid] == target) {
            return true;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

return false;
}

int main() {
    // 定义vector容器并初始化
    std::vector<int> arr = { 1, 5, 7, 15, 20, 25, 30 };

// 在容器中查找目标元素
    int target = 25;
    bool result = binarySearch(arr, target);
    if (result) {
        cout << "元素 " << target << " 在容器中" << endl;
    } else {
        cout << "元素 " << target << " 不在容器中" << endl;
    }

return 0;
}
```
2、顺序查找
原理：
原理是从序列的第一个元素开始遍历，逐个与要查找的元素进行比较，直到找到匹配的元素或遍历完整个序列，如果找到匹配的元素则返回其下标，否则返回-1或一个特定的标志，表示未找到。
缺点：不适合处理大规模的数据
优点：适合处理小规模数据
复杂度：
时间复杂度是O(n)
空间复杂度是O(1)
```cpp
#include <iostream>
using namespace std;
int sequentialSearch(int arr[], int n, int x) {
    for (int i = 0; i < n; ++i) {
        if (arr[i] == x) {
            return i;
        }
    }
    return -1;
}

int main() {
    int arr[] = {3, 2, 5, 1, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 10;

int index = sequentialSearch(arr, n, x);

if (index >= 0) {
        cout << "元素 " << x << " 的位置为 " << index << endl;
    } else {
        cout << "元素 " << x << "不在序列中" << endl;
    }

return 0;
}
```

0.0分

1 人评分

新上线《蓝桥杯辅导》课程，近五年的蓝桥杯省赛与国赛真题都有，从读题开始理解题意、梳理思路、实现代码再提交评测全过程，可有效提升获奖比例甚至进国赛！课程介绍、试听请猛击这里

一只猪

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C++代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

九宫重排（C++代码）

C++常用算法和数据结构（STL）

评论区

精彩推荐

分糖果（C++代码）

C语言训练-大、小写问题（C语言代码）

母牛的故事（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

单词个数统计（C语言代码）

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

简单的a+b （C语言代码）

三角形（C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C++代码）

一只猪

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C++代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

九宫重排 （C++代码）

C++常用算法和数据结构（STL）

评论区

精彩推荐

分糖果 （C++代码）

C语言训练-大、小写问题 （C语言代码）

母牛的故事 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

单词个数统计 （C语言代码）

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

简单的a+b （C语言代码）

三角形 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C++代码）

九宫重排（C++代码）

　　评论区

分糖果（C++代码）

C语言训练-大、小写问题（C语言代码）

母牛的故事（C语言代码）

单词个数统计（C语言代码）

三角形（C语言代码）