c++分治算法

分治算法的策略

简单来说，分治算法的基本思想就是:
把规模大的问题不断分解为子问题，使得问题规模减小到可以直接求解为止。

分治算法

基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。
求出子问题的解，就可得到原问题的解。
即一种分目标完成程序算法，简单问题可用二分法完成。

分治思想的经典应用

-二分查找
-归并排序
-快速排序
-大整数乘法
-Strassen矩阵乘法

二分查找

二分查找的定义
-二分查找（Binary Search）是一种在有序数组中查找特定元素的高效算法
-核心思想：每次将查找范围缩小一半，直到找到目标元素或确定目标元素不存在
二分查找的前提条件
-数组必须是有序的（升序或降序）
-数组元素支持随机访问（如数组，而不是链表）
二分查找的优势
-时间复杂度为O（log n），远优于线性查找的O（n）
-空间复杂度低，迭代实现为O（1）.递归实现为O（log n）

二分查找算法原理

算法步骤
1.初始化查找范围：左边界left=0，右边界right=数组长度-1
2.当left ≤ right时，执行以下操作：
-计算中间位置mid = left +（right - left）/ 2（避免整数溢出）
-如果arr[mid] == 目标值，返回mid
-如果arr[mid] < 目标值，说明目标值在右半部分，更新left = mid + 1
-如果arr[mid] > 目标值，说明目标值在左半部分，更新right = mid - 1
3.如果循环结束仍未找到目标值，返回-1表示不存在

迭代实现

#include<iostream> #include<iomanip> #include<algorithm> using namespace std; int a[1000]; int n; int bfind(int,int,int); int main() { cin>>n; for(int i = 0;i<n;i++) { cin>>a[i]; } sort(a+0,a+n); int x; cin>>x; cout<<bfind(x,0,n-1); return 0; } int bfind(int x,int l,int r) { while(l<=r) { int mid = l + (r-l)/2; if(a[mid] == x) return mid; else if(a[mid]<x) l = mid+1; else if(a[mid]>x) r = mid-1; } return -1; }

递归实现

#include<iostream> #include<iomanip> #include<algorithm> using namespace std; int a[1000]; int n; int bfind(int,int,int); int bfind2(int,int,int); int main() { cin>>n; for(int i = 0;i<n;i++) { cin>>a[i]; } sort(a+0,a+n); int x; cin>>x; cout<<bfind2(x,0,n-1); return 0; } int bfind(int x,int l,int r) { while(l<=r) { int mid = l + (r-l)/2; if(a[mid] == x) return mid; else if(a[mid]<x) l = mid+1; else if(a[mid]>x) r = mid-1; } return -1; } int bfind2(int x,int l,int r) { if(l>r) return -1; int mid = l + (r-l)/2; if(a[mid] == x) return mid; else if(a[mid]>x) return bfind2(x,l,mid-1); else if(a[mid]<x) return bfind2(x,mid+1,r); }

练习题

查找最后一个出现的target

题目描述
给你有序一个数组，级一个target，数据量很大，请你使用二分查找法，查找最后一个出现的target所在的位置（数组索引）
输入格式
2行
第一行一个整数n，数组长度
第二行n个整数，数组元素，空格隔开
第三行—个整数target
输出格式
输出一个整数，最后一个出现的target所在的位置（数组索引），如果没有，输出-1
提示

找到以后，继续向右查找

用例输入
5
1 2 2 3 4
2
用例输出
2

#include<iostream> #include<iomanip> #include<algorithm> using namespace std; int a[1000]; int n; int bfind(int,int,int); int bfind2(int,int,int); int bfind3(int,int,int); int main() { cin>>n; for(int i = 0;i<n;i++) { cin>>a[i]; } sort(a+0,a+n); int x; cin>>x; cout<<bfind2(x,0,n-1); return 0; } int bfind(int x,int l,int r) { while(l<=r) { int mid = l + (r-l)/2; if(a[mid] == x) return mid; else if(a[mid]<x) l = mid+1; else if(a[mid]>x) r = mid-1; } return -1; } int bfind2(int x,int l,int r) { if(l>r) return -1; int mid = l + (r-l)/2; if(a[mid] == x) return mid; else if(a[mid]>x) return bfind2(x,l,mid-1); else if(a[mid]<x) return bfind2(x,mid+1,r); } int bfind3(int x,int l,int r) { int result = -1; while(l<=r) { int mid = l + (r-l)/2; if(a[mid]>x) r = mid-1; else if(a[mid]<x) l = mid+1; else if(a[mid]==x) { if(a[mid-1]!=x) return mid; else l = mid+1; } } return result; }

查找第一个大于等于target的数据

题目描述
给你有序一个数组，级一个target，数据量很大，请你使用二分查找法，查找第一个大于等于目标值的元素的索引
输入格式
2行
第一行一个整数n，数组长度
第二行n个整数，数组元素，空格隔开
第三行一个整数target
输出格式
输出一个整数，第一个大于等于目标值的元素的索引，如果没有，输出-1

用例输入
5
1 2 2 3 4
2
用例输出
1

#include<iostream> #include<iomanip> #include<algorithm> using namespace std; int a[1000]; int n; int bfind(int,int,int); int bfind2(int,int,int); int bfind3(int,int,int); int main() { cin>>n; for(int i = 0;i<n;i++) { cin>>a[i]; } sort(a+0,a+n); int x; cin>>x; cout<<bfind3(x,0,n-1); return 0; } int bfind(int x,int l,int r) { while(l<=r) { int mid = l + (r-l)/2; if(a[mid] == x) return mid; else if(a[mid]<x) l = mid+1; else if(a[mid]>x) r = mid-1; } return -1; } int bfind2(int x,int l,int r) { if(l>r) return -1; int mid = l + (r-l)/2; if(a[mid] == x) return mid; else if(a[mid]>x) return bfind2(x,l,mid-1); else if(a[mid]<x) return bfind2(x,mid+1,r); } int bfind3(int x,int l,int r) { int result = -1; while(l<=r) { int mid = l + (r-l)/2; if(a[mid]>x) r = mid-1; else if(a[mid]<x) l = mid+1; else if(a[mid]==x) { if(a[mid-1]>=x) return mid; else l = mid+1; } } return result; }

查找最后一个小于等于target的数据

题目描述
给你有序一个数组，级一个target，数据量很大，请你使用二分查找法，查找最后一个小于等于目标值的元素的索引
输入格式
2行
第一行一个整数n，数组长度
第二行n个整数，数组元素，空格隔开
第三行一个整数target
输出格式
输出一个整数，最后一个小于等于目标值的元素的索引，如果没有，输出-1

用例输入
5
1 2 2 3 4
2
用例输出
2

#include<iostream> #include<iomanip> #include<algorithm> using namespace std; int a[1000]; int n; int bfind(int,int,int); int bfind2(int,int,int); int bfind3(int,int,int); int main() { cin>>n; for(int i = 0;i<n;i++) { cin>>a[i]; } sort(a+0,a+n); int x; cin>>x; cout<<bfind2(x,0,n-1); return 0; } int bfind(int x,int l,int r) { while(l<=r) { int mid = l + (r-l)/2; if(a[mid] == x) return mid; else if(a[mid]<x) l = mid+1; else if(a[mid]>x) r = mid-1; } return -1; } int bfind2(int x,int l,int r) { if(l>r) return -1; int mid = l + (r-l)/2; if(a[mid] <= x) return mid; else if(a[mid]>x) return bfind2(x,l,mid-1); else if(a[mid]<x) return bfind2(x,mid+1,r); } int bfind3(int x,int l,int r) { int result = -1; while(l<=r) { int mid = l + (r-l)/2; if(a[mid]>x) r = mid-1; else if(a[mid]<x) l = mid+1; else if(a[mid]==x) { if(a[mid-1]>=x) return mid; else l = mid+1; } } return result; }