C++二分查找（练习题）

找左端点【STL二分查找函数法】

【描述】请在一个有序不递减的数组中（数组中有相等的值），采用二分查找，找到值 x 第 1 次出现的位置，如果不存在x 请输出-1。
【输入描述】
第一行，一个整数n，代表数组元素个数（n <= 106）
第二行，n个数，代表数组的n个递增元素
第三行，一个整数x，代表要查找的数
【输出描述】
x在数组中的位置，位置从1开始编号；没找到，输出-1。
【输入用例】
9
3 3 3 4 9 11 13 15 17
3
【输出用例】
1

#include<iostream>#include<algorithm>usingnamespacestd;inta[110];intn,x;intmain(){cin>>n;for(inti=1;i<=n;i++){cin>>a[i];}cin>>x;// 先找第一个>=x的值的位置idintid=lower_bound(a+1,a+n+1,x)-a;if(id>n||a[id]!=x)// 没找到，或者只找到>x的值cout<<-1;elsecout<<id;return0;}/* 【输入用例2】 10 1 3 5 7 9 11 13 15 17 19 20 【输出用例2】 -1 【输入用例3】 10 1 3 5 7 9 11 13 15 17 19 -2 【输出用例3】 -1 【输入用例4】 10 1 3 3 3 9 11 13 15 17 19 3 【输出用例4】 2 【输入用例5】 10 1 9 11 13 15 17 19 20 20 20 20 【输出用例5】 8 【输入用例6】 10 12 6 9 23 35 69 75 15 45 33 69 【输出用例6】 6 */

查找元素

【描述】使用STL的lower_bound函数查找数组中第一个大于等于目标值的元素位置
【输入描述】
输入为三行，第一行为数组元素，数组元素不超过100个；第二行输入需要查找的值,第三行为数组元素
【输出描述】
输出查找的结果
【输入用例1】
10
35
10 20 30 40 50 60 70 80 90 100
【输出用例1】
第一个大于等于 35 的元素在索引 3 处，值为 40
【输入用例2】
10
110
10 20 30 40 50 60 70 80 90 100
【输出用例2】
没有找到大于等于 110 的元素

#include<iostream>#include<algorithm>usingnamespacestd;voidstlLowerBound(){intarr[100];//数据数组intn;inttarget;cin>>n;cin>>target;//输入查找值for(inti=0;i<n;i++){cin>>arr[i];//输入元素}int*pos=lower_bound(arr,arr+n,target);if(pos!=arr+10)cout<<"第一个大于等于 "<<target<<" 的元素在索引 "<<(pos-arr)<<" 处，值为 "<<*pos<<endl;elsecout<<"没有找到大于等于 "<<target<<" 的元素"<<endl;}intmain(){stlLowerBound();return0;}/* 【输入用例2】 5 3 1 2 3 4 5 【输出用例2】 第一个大于等于 3 的元素在索引 2 处，值为 3 【输入用例3】 6 2 2 2 3 3 4 4 【输出用例3】 第一个大于等于 2 的元素在索引 0 处，值为 2 【输入用例4】 3 0 5 6 7 【输出用例4】 第一个大于等于 0 的元素在索引 0 处，值为 5 【输入用例5】 5 3 3 1 4 2 5 【输出用例5】 第一个大于等于 3 的元素在索引 2 处，值为 4 【输入用例6】 10 16 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 【输出用例6】 没有找到大于等于 16 的元素 */

统计次数

【描述】在有序数组中统计某个元素的出现次数
【输入描述】
输入为三行，第一行为数组元素，数组元素不超过100个；第二行输入需要查找的值，第三行为数组元素
【输出描述】
输出该数字出现的次数
【输入用例】
10
110
10 20 30 40 50 60 70 80 90 100
【输出用例】
元素 110 出现了 0 次

#include<iostream>#include<algorithm>usingnamespacestd;voidcountOccurrences(){intarr[100];//数据数组intn;inttarget;cin>>n;cin>>target;//输入查找值for(inti=0;i<=n;i++){cin>>arr[i];//输入元素}// 使用STL函数intfirst=lower_bound(arr,arr+n,target)-arr;intlast=upper_bound(arr,arr+n,target)-arr;intcount=last-first;cout<<"元素 "<<target<<" 出现了 "<<count<<" 次";}intmain(){countOccurrences();return0;}/* 【输入用例2】 5 2 1 2 2 3 4 【输出用例2】 元素 2 出现了 2 次 【输入用例3】 4 5 1 3 5 7 【输出用例3】 元素 5 出现了 1 次 【输入用例4】 4 5 2 4 6 8 【输出用例4】 元素 5 出现了 0 次 【输入用例5】 3 4 1 2 3 【输出用例5】 元素 4 出现了 0 次 【输入用例6】 4 5 5 5 5 5 【输出用例6】 元素 5 出现了 4 次 */

寻找峰值

【描述】输入一个数组，找出该数组的局部（左半部分或右半部分）最大值，数组的元素为在10个以内。
【输入描述】
输入为一行，是需要的被查找的数组元素
【输出描述】
输出该数组峰值数的索引值与本身值
【输入用例】
6
1 2 4 5 3 1
【输出用例】
峰值在索引 3，值为 5

#include<iostream>#include<algorithm>// 用于max_elementusingnamespacestd;voidfindGlobalMax(){intarr[100],n;cin>>n;for(inti=0;i<n;i++){cin>>arr[i];}// 用algorithm找全局最大值，通过索引访问intmaxIndex=max_element(arr,arr+n)-arr;// 直接计算索引cout<<"峰值在索引 "<<maxIndex<<"，值为 "<<arr[maxIndex]<<endl;}intmain(){findGlobalMax();return0;}/* 【输入用例2】 5 1 3 2 4 5 【输出用例2】 峰值在索引 4，值为 5 【输入用例3】 3 5 4 3 【输出用例3】 峰值在索引 0，值为 5 【输入用例4】 4 1 2 3 4 【输出用例4】 峰值在索引 3，值为 4 【输入用例5】 5 5 4 3 2 1 【输出用例5】 峰值在索引 0，值为 5 【输入用例6】 5 1 5 2 6 3 【输出用例6】 峰值在索引 3，值为 6 */

寻找旋转排序数组中的目标值

【描述】输入一个旋转排序数组，找出需要寻找的目标元素，输出该元素的相关信息
【输入描述】
输入为三行，第一行是数字元素个数（不超过100），第二行为需要寻找的目标值，第三行为该数组元素。
【输出描述】
输出目标值信息
【输入用例1】
10
2
5 4 5 6 7 0 1 2 1
【输出用例1】
找到目标值 2 在索引 7
【输入用例2】
10
0
5 4 5 6 7 1 1 2 1
【输出用例2】
未找到目标值 0

#include<iostream>#include<algorithm>usingnamespacestd;voidsearchArray(){intarr[100];//数据数组intn;inttarget;cin>>n;cin>>target;for(inti=0;i<=n;i++){cin>>arr[i];//输入元素}intleft=0,right=8;while(left<=right){intmid=left+(right-left)/2;if(arr[mid]==target){cout<<"找到目标值 "<<target<<" 在索引 "<<mid;return;}// 判断哪一部分是有序的if(arr[left]<=arr[mid]){// 左半部分有序if(arr[left]<=target&&target<arr[mid]){// 目标值在左半部分right=mid-1;}else{// 目标值在右半部分left=mid+1;}}else{// 右半部分有序if(arr[mid]<target&&target<=arr[right]){// 目标值在右半部分left=mid+1;}else{// 目标值在左半部分right=mid-1;}}}cout<<"未找到目标值 "<<target<<endl;}intmain(){searchArray();return0;}/* 【输入用例1】 10 2 5 4 5 6 7 0 1 2 1 【输出用例1】 找到目标值 2 在索引 7 【输入用例2】 10 0 5 4 5 6 7 1 1 2 1 【输出用例2】 未找到目标值 0 【输入用例3】 7 3 1 2 3 4 5 6 7 【输出用例3】 找到目标值 3 在索引 2 【输入用例4】 7 8 4 5 6 7 0 1 2 【输出用例4】 未找到目标值 8 【输入用例5】 1 5 5 【输出用例5】 找到目标值 5 在索引 0 */

寻找多个数值

【描述】输入一个数组，再输入一些数值，判断这些数是否存在在该数组中
【输入描述】
输入为四行，第一行为被寻找数组元素个数，第二行为被寻找数组元素；第三行为寻找数组的元素个数，第四行为寻找数组元素。
【输出描述】
输出目标值被找到情况
【输入用例】
10
1 2 3 4 5 6 7 8 9 10
4
3 6 9 12
【输出用例】
目标值 3 在数组中找到
目标值 6 在数组中找到
目标值 9 在数组中找到
目标值 12 未找到

#include<iostream>#include<algorithm>usingnamespacestd;voidsearchMultipleTargets(){intarr[100];//数据数组intn,m;inttargets[100];cin>>n;for(inti=0;i<n;i++){cin>>arr[i];//输入元素}cin>>m;for(inti=0;i<m;i++){cin>>targets[i];//输入元素}for(inti=0;i<m;i++){inttarget=targets[i];intleft=0,right=n-1;boolfound=false;while(left<=right){intmid=left+(right-left)/2;if(arr[mid]==target){found=true;break;}elseif(arr[mid]<target){left=mid+1;}else{right=mid-1;}}if(found)cout<<"目标值 "<<target<<" 在数组中找到"<<endl;elsecout<<"目标值 "<<target<<" 未找到"<<endl;}}intmain(){searchMultipleTargets();return0;}/* 【输入用例2】 5 1 3 5 7 9 2 5 4 【输出用例2】 目标值 5 在数组中找到 目标值 4 未找到 【输入用例3】 3 2 4 6 1 2 【输出用例3】 目标值 2 在数组中找到 【输入用例4】 4 10 20 30 40 1 40 【输出用例4】 目标值 40 在数组中找到 【输入用例5】 5 5 10 15 20 25 1 18 【输出用例5】 目标值 18 未找到 【输入用例6】 6 2 4 6 8 10 12 3 6 9 12 【输出用例6】 目标值 6 在数组中找到 目标值 9 未找到 目标值 12 在数组中找到 */