# 34. Search for a Range

Description:

https://leetcode.com/problems/search-for-a-range/#/description

Algorithm:

1. Use find() to determine whether the target is in the array.
2. Left = 0, right = size – 1;
3. Squeeze left and right to find middle s.t. nums[middle] == target
4. Squeeze left and middle to find left s.t.  nums[left] == target
5. Squeeze right and middle to find right s.t.  nums[right] == target

Code:

``` class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { vector <int> result; vector<int>::iterator iter = std::find(nums.begin(), nums.end(), target); if (iter == nums.end()) { result.push_back(-1); result.push_back(-1); return result; }```

``` int left = 0; int right = nums.size() - 1; int middle_left, middle_right; while (nums[left] < nums[right]) { int middle = (left + right) / 2; if (nums[middle] < target) left = middle + 1; else if (nums[middle] > target) right = middle - 1; else { int middle_save = middle; while (nums[left] < target) { middle_left = (middle + left) / 2; if (nums[middle_left] < target) left = middle_left + 1; else middle = middle_left - 1; } ```

```middle = middle_save; while (nums[right] > target) { middle_right = (middle + right) / 2; if (nums[middle_right] > target) right = middle_right - 1; else middle = middle_right + 1; } } } result.push_back(left); result.push_back(right); return result; } };```

Timing: beat 47.5%. 9ms

Best is 6ms.

Code for 6ms algorithm:

``` class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { vector<int> res(2, -1); if(nums.size()==0) return res; int left = 0, right = nums.size() - 1; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] < target) left = mid + 1; else right = mid; // Not symm here } if (nums[right] != target) return res; res[0] = right; right=nums.size()-1; while(left<=right){ int mid=(left+right)/2; if(nums[mid]>target) right=mid-1; else left=mid+1; } res[1]=right;```

``` ```

```return res; } };```