fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6.  
  7.     vector<int> searchRange(vector<int>& nums, int target) {
  8.         vector<int> ans(2, -1);
  9.         int s = 0;
  10.         int e = nums.size() - 1;
  11.         bool found = false;
  12.  
  13.  
  14.         while (s <= e) {
  15.             int mid = s + (e - s) / 2;
  16.             if (nums[mid] == target) {
  17.                 found = true;
  18.                 break;
  19.             } else if (nums[mid] < target) {
  20.                 s = mid + 1;
  21.             } else {
  22.                 e = mid - 1;
  23.             }
  24.         }
  25.  
  26.         if (!found) {
  27.             return ans;
  28.         }
  29.  
  30.         int low = 0;
  31.         int high = nums.size() - 1;
  32.         int start = -1;
  33.         int end = -1;
  34.  
  35.  
  36.         while (low <= high) {
  37.             int mid = low + (high - low) / 2;
  38.             if (nums[mid] == target) {
  39.                 end = mid;
  40.                 low = mid + 1;
  41.             } else if (nums[mid] < target) {
  42.                 low = mid + 1;
  43.             } else {
  44.                 high = mid - 1;
  45.             }
  46.         }
  47.  
  48.  
  49.         low = 0;
  50.         high = nums.size() - 1;
  51.         while (low <= high) {
  52.             int mid = low + (high - low) / 2;
  53.             if (nums[mid] == target) {
  54.                 start = mid;
  55.                 high = mid - 1;
  56.             } else if (nums[mid] > target) {
  57.                 high = mid - 1;
  58.             } else {
  59.                 low = mid + 1;
  60.             }
  61.         }
  62.  
  63.         ans[0] = start;
  64.         ans[1] = end;
  65.  
  66.         return ans;
  67.     }
  68.  
  69.  
  70. int main() {
  71.     int n;
  72.     cin>>n;
  73.  
  74.         int target;
  75.     cin >> target;
  76.  
  77.  
  78.     vector<int> nums(n);
  79.     for (int i = 0; i < n; i++) {
  80.         cin >> nums[i];
  81.     }
  82.  
  83.  
  84.  
  85.  
  86.     vector<int> result = searchRange(nums, target);
  87.  
  88.     cout << result[0] << " " << result[1] << endl;
  89.  
  90.     return 0;
  91. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
6 8
5 7 7 8 8 10
stdout
copy 
3 4
https://ideone.com/2Mhh2M
language:
C++14 (gcc 8.3)
created:
15 hours 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!