Solution: Number Range

Problem Statement

Given an array of numbers sorted in ascending order, find the range of a given number ‘key’. The range of the ‘key’ will be the first and last position of the ‘key’ in the array.

Write a function to return the range of the ‘key’. If the ‘key’ is not present return [-1, -1].

Example 1:

Input: [4, 6, 6, 6, 9], key = 6
Output: [1, 3]

Example 2:

Input: [1, 3, 8, 10, 15], key = 10
Output: [3, 3]

Example 3:

Input: [1, 3, 8, 10, 15], key = 12
Output: [-1, -1]

Constraints:

0 <= nums.length <= 10<sup>5</sup>

.....

Like the course? Get enrolled and start learning!

lejafilip

· 2 years ago

  vector<int> findRange(const vector<int> &arr, int key) {
    vector<int> result(2, -1);
    
    auto n = arr.size() - 1;
    if(arr[n] < key)
      return result;
    else if(arr[0] > key)
      return result;
    
    result[0] = findLeftIdx(arr, key, 0, n);
    result[1] = findRightIdx(arr, key, 0, n);

    return result;
  }

  int findLeftIdx(const vector<int> &arr, int key, int start, int end)
  {
    auto pivot = (start + end) / 2;
    if(start >= end)
    {
      if(arr[pivot] == key)
        return pivot;
      else if(pivot < arr.size() - 1 && arr[pivot + 1] == key)
        return pivot + 1;
      else
        return -1;
    }

    if(arr[pivot] >= key)
      return findLeftIdx(arr, key, start, pivot - 1);
    else
      return findLeftIdx(arr, key, pivot + 1, end);
  }