Advertisement
vaibhav1906

Find First and Last Position of Element in Sorted Array

Nov 24th, 2021
1,298
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.12 KB | None | 0 0
  1. class Solution {
  2. public:
  3.     vector<int> searchRange(vector<int>& nums, int target) {
  4.        
  5.         int n = nums.size();
  6.         if(n==0)return {-1,-1};
  7.         //First Binary search to find first true for the condition nums[m] >= target
  8.         int l = 0, h = n-1;
  9.         while(l<h){
  10.             int m = l + (h-l)/2;
  11.            
  12.             if(nums[m]>=target){
  13.                 h = m;
  14.             }
  15.             else{
  16.                 l  = m+1;
  17.             }
  18.            
  19.         }
  20.        
  21.         if(nums[l]!=target) return {-1,-1};//To check either target is present or not
  22.        
  23.         int startIndex = l ;
  24.        
  25.         //Second binary search to find last false for the condition nums[m]>target
  26.        
  27.         l = 0;
  28.         h = n-1;
  29.        
  30.         while(l<h){
  31.            
  32.             int m = l + (h-l+1)/2;
  33.            
  34.             if(nums[m]>target){
  35.                 h = m-1;
  36.             }
  37.             else{
  38.                 l = m;
  39.             }
  40.            
  41.         }
  42.        
  43.         int endIndex = l;
  44.        
  45.         return {startIndex,endIndex};
  46.        
  47.        
  48.     }
  49. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement