Search for a Range

---

 

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,

Given [5, 7, 7, 8, 8, 10] and target value 8,

return [3, 4].

---

 

1 class Solution { 2 public: 3     vector
     
       searchRange(int A[], int n, int target) { 4         vector
      
        range(2, -1); 5         int lower = 0; 6         int upper = n; 7         int mid; 8  9         // Search for lower bound10         while (lower < upper) {11             mid = (lower + upper) / 2;12             if (A[mid] < target)13                 lower = mid + 1;14             else15                 upper = mid;16         }17 18         // If the target is not found, return (-1, -1)19         if (A[lower] != target)20             return range;21         range[0] = lower;22 23         // Search for upper bound24         upper = n;25         while (lower < upper) {26             mid = (lower + upper) / 2;27             if (A[mid] > target)28                 upper = mid;29             else30                 lower = mid + 1;31         }32         range[1] = upper - 1;33 34         return range;35     }36 };