分治 二分查找
教程导读
学研发网的这篇信息学奥赛技术教程文章主要介绍了分治 二分查找,现在分享给大家,供学习和参考。文章包含3123字,纯文字阅读大概需要8分钟。
教程信息
二分查找
通过题目解题认识二分查找
题目来源:
https://www.luogu.com.cn/problem/P2249
题目内容:
(一)顺序查找
顺序查找(Sequential Search
),也称为线性查找,是一种简单直观的查找算法,用于在无序数组
或列表中查找特定元素。
顺序查找就是从数组的第一个元素开始,依次遍历每个元素,比较当前元素与目标元素是否相等。
顺序查找算法是一种简单直观的查找方法,适用于小规模的无序数组或列表。然而,它的时间复杂度较高,为O(n),
其中n是数组或列表的大小。这意味着在较大规模的数据集上,顺序查找的效率较低。
由于顺序查找算法的简单性,它适用于简单的查找任务或者在特定场景中,当数据量较小且没有明显的结构时,可以选择使用顺序查找。对于有序数组或列表,二分查找等更高效的算法通常更合适。
实现代码:
#include<bits/stdc++.h> using namespace std; int main() { // n 数据数量 // m 询问词数 int n,m; // 读入n,m信息 cin>>n>>m; // 定义标识 bool flag=false; // 定义数据数组和询问数组 并初始化数据 int a[n],b[m]; for (int i=0;i<n;i++){ cin>>a[i]; } for (int i=0;i<m;i++){ cin>>b[i]; } // 通过循环查询的方式遍历获取数据 for (int i=0;i<m;i++) { for (int j=0;j<n;j++){ if(a[j]==b[i]) { cout<<j+1<<" "; flag=true; break; } } if(flag==false){ cout<<-1<<" "; } flag=false; } }
执行结果:
(二)二分查找
1、二分查找的思想
二分查找首先要求数据从小到大进行排序
,然后从中间的数字开始查找
。
若序列中最中间的数字等于要找的数字,直接返回即可;
若这个数字小于要找的数字,由于序列升序,因此序列的前半段显然都小于我们寻找的目标,只需要从序列的后半段寻找即可;
若这个数字大于要找的数字,只要从前半段寻找即可。
例如查找数字1的数组下标:
2、手写二分查找
(1)一般性的二分查找代码
实现代码:
#include<bits/stdc++.h> using namespace std; // 原始数据 int arr[] = { 1, 3, 3, 3, 5, 7, 9, 11, 13, 15, 17 }; // 查找的函数 int binarySearch(int target) { // 左边界 int left = 0; // 右边界 int right = 10; while (left <= right) { // 有时 l+r 可能会超过 int 类型的极限,可以改成left + (right - left) / 2 int mid = (right + left) / 2; // 输出过程日志 // cout<<left<<"_"<<arr[left]<<"---"<<right<<"_"<<arr[right]<<"---"<<mid<<"_"<<arr[mid]<<endl; if (arr[mid] == target) { // 找到目标元素,返回索引 return mid; } else if (arr[mid] < target) { // 目标元素在右半部分,更新左边界 left = mid + 1; } else { // 目标元素在左半部分,更新右边界 right = mid - 1; } } // 目标元素不存在,返回-1 return -1; } int main() { // 待查找的目标元素 int target = 11; // 获取查找结果 int result = binarySearch(target); if (result != -1) { cout << "目标元素 " << target << " 的索引为: " << result <<endl; } else { cout << "目标元素 " << target << " 不存在于数组中" <<endl; } return 0; }
执行结果:
(2)递归实现的二分查找
实现代码:
#include<bits/stdc++.h> using namespace std; int arr[] = { 1, 3, 3, 3, 5, 7, 9, 11, 13, 15, 17 }; int binarySearchRecursive(int target, int left, int right) { if (left > right) { // 目标元素不存在,返回-1 return -1; } int mid = left + (right - left) / 2; if (arr[mid] == target) { // 找到目标元素,返回索引 return mid; } else if (arr[mid] < target) { // 目标元素在右半部分,递归查找 return binarySearchRecursive(target, mid + 1, right); } else { // 目标元素在左半部分,递归查找 return binarySearchRecursive(target, left, mid - 1); } } int main() { int target = 1; int left = 0; int right = 10; int result = binarySearchRecursive(target, left, right); if (result != -1) { cout << "目标元素 " << target << " 的索引为: " << result <<endl; } else { cout << "目标元素 " << target << " 不存在于数组中" <<endl; } return 0; }
执行结果:
3、利用C/C++自带函数实现
(1)C/C++自带函数
①lower_bound(begin,end,val)
:在有序数组 [begin,end) 中找到第一个大于等于 val 的值并返回其位置。
②upper_bound(begin,end,val)
:在有序数组[begin,end)中找到第一个大于 val 的值并返回其位置。
③binary_search(begin,end,val)
:在有序数组[begin,end)中判断是否存在val,存在返回true,不存在返回false
实现代码:
#include<bits/stdc++.h> using namespace std; int main() { int n,m; cin>>n>>m; int a[n],b[m]; for (int i=0;i<n;i++) cin>>a[i]; for (int i=0;i<m;i++) cin>>b[i]; for (int i=0;i<m;i++) { if(binary_search(a,a+n,b[i])==false) { cout<<-1<<" "; } else { cout<<(lower_bound(a,a+n,b[i])-a)+1<<" "; } } return 0; }
执行结果:
教程咨询
如果章节内容看不懂,可以联系作者。
教程总结
以上是学研发网为您提供分治 二分查找的全部内容,希望教程文章能够帮你了解学习分治 二分查找,解决所遇到的问题。 如果觉得学研发网信息学奥赛教程内容还不错,欢迎将学研发网网站推荐给身边需要的人。
教程备注
版权声明:教程内容为学研发网整理和编写,如需转载请联系站长并附上文章原始链接和原始作者信息。
手机阅读
扫描二维码推送至手机访问。
本文链接:http://www.xueyanfa.com/xinaojiaocheng/xinaozhongji-262.html