C/C++:和为给定数(二分查找,快速排序)
题目描述(题目链接)
给出若干个整数，询问其中是否有一对数的和等于给定的数。
输入格式
共三行：
第一行是整数n(0 < n <= 100,000)，表示有n个整数。
第二行是n个整数。整数的范围是在0到108之间。
第三行是一个整数m（0 <= m <= 230)，表示需要得到的和。
输出格式
若存在和为m的数对，输出两个整数，小的在前，大的在后，中间用单个空格隔开。
若有多个数对满足条件，选择数对中较小的数更小的。若找不到符合要求的数对，输出一行No。
样例输入
4
2 5 1 4
6
样例输出
1 5
解题思路：
给一个数组a，要求结果是一对数小的在前大的在后，要求找出数对中较小的数最小的那个数对
- 显然我们要先对这个数组进行一个升序排序，
- 排序完后，可以看出a[0]+a[n-1]就是以a[0]为较小数所能产生的最大的和，如果
x>a[0]+a[n-1],那么就排除a[0]了， - 由此可推断出，开两个两个变量
left=0,right=n-1,因为已经排序过是有序数组了，left和right作为数组的两端，如果x>a[left]+a[right],则区间左端left自增，如果x<a[left][right],则区间右端right自减，这样也能保证找出符合题意的数对中较小的数最小的那个数对 - 很像二分的思路
参考代码：
C++：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
void fun(ll a[],ll x,ll left,ll right)
{while(left<right){if(x>a[left]+a[right])left++;else if(x<a[left]+a[right])right--;else if(x==a[left]+a[right])break;}if(left<right)//如果左端点大于了右端点说明不存在cout<<a[left]<<" "<<a[right];elsecout<<"No";
}
int main()
{cin>>n;ll a[n];for(int i=0;i<n;i++)cin>>a[i];ll m;cin>>m;sort(a,a+n);//升序排序，变为有序数组fun(a,m,0,n-1);//数组两端return 0;
}
斯，写多了c++,一遇到排序就想用sort(),太偷懒了，c没有这个函数，冒泡会超时，又去看了遍快速排序，才过了
简单说下快速排序的步骤：
- 选择一个基准元素(通常是序列的第一个元素,或者最后一个元素)
- 将序列中小于基准元素的元素放在基准元素的左边,大于基准元素的元素放在基准元素的右边,等于基准元素的元素可以放在任意一边
- 对基准元素左右两边的子序列分别递归地进行快速排序
C:
#include<stdio.h>
typedef long long ll;
int n;
void fun(ll a[],ll x,ll left,ll right)
{while(left<right){if(x>a[left]+a[right])left++;else if(x<a[left]+a[right])right--;elsebreak;}if(left<right)printf("%lld %lld",a[left],a[right]);elseprintf("No");
}
void swap(ll *a,ll *b)//交换赋值,
{ll t=*a;*a=*b;*b=t;
}
int partition(long long a[], int low, int high) {//定义一个分区函数，用于将数组分成两部分，使得左边的元素都小于基准元素，右边的元素都大于基准元素long long pivot = a[high];//基准元素,设置为数组最后一个元素int i = low - 1;//初始化一个指针i，用于记录小于基准元素的元素的个数for (int j = low; j < high; j++) {//遍历数组，将小于基准元素的值放到左边，大于基准元素的值放到右边if (a[j] < pivot) {i++;swap(&a[i], &a[j]);}}swap(&a[i + 1], &a[high]);return i + 1;
}
void quickSort(long long a[], int low, int high) {//接收一个整型数组arr和两个整数low和high作为参数，表示待排序数组的起始下标和结束下标if (low < high) {//判断是否需要进行排序，如果low小于high，说明数组中至少有两个元素，需要进行排序int pi = partition(a, low, high);//用partition函数，获取基准元素的下标quickSort(a, low, pi - 1);//对基准元素左边的子数组进行快速排序quickSort(a, pi + 1, high);//对基准元素右边的子数组进行快速排序}
}
int main()
{scanf("%d",&n);ll a[n];for(int i=0;i<n;i++)scanf("%lld",&a[i]);ll m;scanf("%lld",&m);quickSort(a,0,n-1);fun(a,m,0,n-1);return 0;
}