## Thursday, November 13, 2014

### [LeetCode] 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]`.

4 5 8 8 8 8 9 9 10
target = A[mid=4] = 8

4 5 8 8
target != A[mid]，搜索 A[mid+1 : end]。
8
target = A[mid]，搜索A[start: mid-1]
start > end，left = start

8 9 9 10
target != A[mid]，搜索A[start : mid-1]。
8
target = A[mid]，搜索A[mid+1 : end]。
start > end，right = end

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39``` ```class Solution { public: vector searchRange(int A[], int n, int target) { vector range; range.push_back(findLeftMost(A, n, target)); range.push_back(findRightMost(A, n, target)); return range; } int findLeftMost(int A[], int n, int target) { int start = 0, end = n-1; while(start<=end) { int mid = start + (end-start)/2; if(targetA[mid]) start = mid+1; else end = mid-1; } if(start>=0 && startA[mid]) start = mid+1; else start = mid+1; } if(end>=0 && end

1. This comment has been removed by the author.

2. 这个算法worst case 也是o(n)吧

3. findLeftMost和findRightMost可以合并成一个循环，当找到target的第一次出现的位置mid的时候，令left = mid，right = A.size()-1，继续循环即可。

1. if (nums[mid] == target)
{
// If we haven't find the first appearance of target, and current is not the first appearance of target
// keep going left.
if (result.empty() && (mid > 0 && nums[mid - 1] == target)) // go left to find the first target
{
right = mid - 1;
}
else if (!result.empty() && (mid < nums.size() -1 && nums[mid + 1] == target)) // If we have found the first apperance of target, go right to find the last appearance of target
{
left = mid + 1;
}
else
{
result.push_back(mid);
if (result.size() == 1)
{
// So now nums[mid] is the first appearance of target, now we need to find the last appearance of target.
// rest left = mid + 1 and right to end of nums,
left = mid;
right = nums.size() - 1;
}
else
{
break;
}
}
}