fork download
copy 
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5.  vector<int> searchRange(vector<int>& nums, int target) {
  6.         vector<int>ans;
  7.         int n=nums.size();
  8.  
  9.         int low=0;
  10.         int high=n-1;
  11.         int l1=-1;
  12.         while(low<=high){
  13.             int mid=(low+high)/2;
  14.             if(nums[mid]==target){
  15.                 l1=mid;
  16.                 high=mid-1;
  17.             }
  18.             else if(nums[mid]>target){
  19.                 high=mid-1;
  20.             }
  21.             else{
  22.                 low=mid+1;
  23.             }
  24.         }
  25.  
  26.         ans.push_back(l1);
  27.  
  28.         int h1=-1;
  29.         low=0;
  30.         high=n-1;
  31.         while(low<=high){
  32.             int mid=(low+high)/2;
  33.             if(nums[mid]==target){
  34.                 h1=mid;
  35.                 low=mid+1;
  36.             }
  37.             else if(nums[mid]>target){
  38.                 high=mid-1;
  39.             }
  40.             else{
  41.                 low=mid+1;
  42.             }
  43.         }
  44.  
  45.         ans.push_back(h1);
  46.  
  47.         return ans;
  48.  
  49.  
  50.     }
  51.  
  52. int main() {
  53. 	int n;
  54. 	cin>>n;
  55. 	vector<int>arr(n);
  56. 	for(int i=0;i<n;i++){
  57. 		cin>>arr[i];
  58. 	}
  59. 	int target;
  60. 	cin>>target;
  61.  
  62. 	vector<int>ans=searchRange(arr,target);
  63. 	cout<<"Lower bound: "<<ans[0]<<" Upper bound: "<<ans[1]<<endl;
  64. 	return 0;
  65. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
6
1 1 1 2 3 3 
3
stdout
copy 
Lower bound: 4 Upper bound: 5
https://ideone.com/EmBEjr
language:
C++ (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!