Karellism

LeetCode C++ Binary Search

Mar 13th, 2019
255
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     vector<int> searchRange(vector<int>& nums, int target) {
  4.         vector<int> result;
  5.         int left_i = searchLeftIndex(nums, target),
  6.             right_i = searchRightIndex(nums, target);
  7.            
  8.         cout << left_i << endl;
  9.         cout << right_i << endl;
  10.         if (left_i < nums.size() && nums[left_i] == target) {
  11.             result.push_back(left_i);
  12.             result.push_back(right_i);
  13.         } else {
  14.             result.push_back(-1);
  15.             result.push_back(-1);            
  16.         }
  17.         return result;
  18.     }
  19.    
  20.     int searchLeftIndex(vector<int>& nums, int target) {
  21.         int left = 0, right = nums.size();
  22.         while(left < right) {
  23.             int mid = left + (right - left)/2;
  24.             if (nums[mid] >= target) {
  25.                 right = mid;
  26.             } else {
  27.                 left = mid + 1;
  28.             }
  29.         }
  30.         return left;
  31.     }
  32.    
  33.     int searchRightIndex(vector<int>& nums, int target) {
  34.         int left = 0, right = nums.size();
  35.         while(left < right) {
  36.             int mid = left + (right - left)/2;
  37.             if (nums[mid] > target) {
  38.                 right = mid;
  39.             } else {
  40.                 left = mid + 1;
  41.             }
  42.         }
  43.         return right-1;        
  44.     }
  45. };
Add Comment
Please, Sign In to add comment