Link to the problem

The problem is here: https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/

Problem description

The problem is very straightforward. Given a sorted array (ascending) nums and a number target, find the starting and the ending position of target.

Idea

This is a very typical problem that can be solved by using binary search.

Binary search

The boundary conditions are essentially important for a bug-free binary search algorithm. My method is to figure out the loop invariant and then strictly follow that invariant. There could be some corner cases that violate the loop invariant at the very beginning. We should handle those cases carefully.

Implementation

STL

The c++ standard library actually provides [std::lower_bound](https://www.cplusplus.com/reference/algorithm/lower_bound/) and [std::upper_bound](https://www.cplusplus.com/reference/algorithm/upper_bound/), which can be used to solve this problem directly.

lower_bound is to find the first element >= target (not less than) upper_bound is to find the first element > target (strictly greater)

DIY

This is my implementation:

  1. class Solution {
  2.     // return the position of first element >= target; -1 if no such element
  3.     int lower_bound(const vector<int> &nums, const int target) {
  4.         // handle special corner cases
  5.         if (nums.empty() || nums.back() < target) {
  6.             return -1;
  7.         }
  8.         if (nums[0] >= target) {
  9.             return 0;
  10.         }
  12.         int i = 0, j = nums.size() - 1;
  13.         // loop inv: nums[i] < target and nums[j] >= target
  14.         while (i < j - 1) {
  15.             if (nums[i] >= target || nums[j] < target) {
  16.                 return -1;
  17.             }
  18.             int mid = (i + j) / 2;
  19.             if (nums[mid] < target) {
  20.                 i = mid;
  21.             } else {
  22.                 j = mid;
  23.             }
  24.         }
  25.         return j >= 0 && nums[j] >= target ? j : -1;
  26.     }
  28.     // return the position of the first element > target; -1 if no such element
  29.     int upper_bound(const vector<int> &nums, const int target) {
  30.         // handle special corner cases
  31.         if (nums.empty() || nums.back() <= target) {
  32.             return -1;
  33.         }
  34.         if (nums[0] > target) {
  35.             return 0;
  36.         }
  38.         int i = 0, j = nums.size() - 1;
  39.         // loop inv: nums[i] <= target and nums[j] > target
  40.         while (i < j - 1) {
  41.             if (nums[i] > target || nums[j] <= target) {
  42.                 return -1;
  43.             }
  44.             int mid = (i + j) / 2;
  45.             if (nums[mid] <= target) {
  46.                 i = mid;
  47.             } else {
  48.                 j = mid;
  49.             }
  50.         }
  51.         return j >= 0 && nums[j] > target ? j : -1;
  52.     }
  54. public:
  55.     vector<int> searchRange(vector<int>& nums, int target) {
  56.         int n = nums.size();
  57.         int i = 0, j = n - 1;
  58.         vector<int> res(2, -1);
  59.         auto lb = this->lower_bound(nums, target);
  60.         auto ub = this->upper_bound(nums, target);
  61.         if (lb == -1 || nums[lb] != target) {
  62.             // can not find target
  63.         } else {
  64.             res[0] = lb;
  65.             res[1] = ub == -1 ? n - 1 : ub - 1;
  66.         }
  67.         return res;
  68.     }
  69. };

Possible refinement:

  • Can use template-programming to reuse code.