## Thursday, January 3, 2013

### [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]`.
» Solve this problem

[解题思路]

[Code]
``````1:       vector<int> searchRange(int A[], int n, int target) {
2:            // Start typing your C/C++ solution below
3:            // DO NOT write int main() function
4:            vector<int> range;
5:            int index = searchTarget(A, 0, n-1, target);
6:            if(index == -1)
7:            {
8:                 range.push_back(-1);
9:                 range.push_back(-1);
10:            }
11:            else
12:            {
13:                 int is = index;
14:                 while(is>0 && A[is-1] == A[index]) is--;
15:                 int ie = index;
16:                 while(ie<n-1 && A[ie+1] == A[index]) ie++;
17:                 range.push_back(is);
18:                 range.push_back(ie);
19:            }
20:            return range;
21:       }
22:       int searchTarget(int A[], int start, int end, int target)
23:       {
24:            if(start > end) return -1;
25:            int mid = (start+end)/2;
26:            if(A[mid] == target) return mid;
27:            if(A[mid]<target)
28:            return searchTarget(A, mid+1, end, target);
29:            else
30:            return searchTarget(A, start, mid-1, target);
31:       }
``````

[Note]
1. Line 6

Update: 07/15/2013 Refactor the code

``````1:    vector<int> searchRange(int A[], int n, int target) {
2:      vector<int> result;
3:      result.push_back(-1);
4:      result.push_back(-1);
5:      // find the low bound of the range, O(lgn)
6:      int start =0, end =n-1;
7:      while(start < end)
8:      {
9:        int mid = (start + end)/2;
10:        if(A[mid] < target)
11:        {
12:          start = mid + 1;
13:          continue;
14:        }
15:        end = mid;
16:      }
17:      int low_bound = A[start] == target? start:-1;
18:      if(low_bound == -1)
19:      {
20:        return result;
21:      }
22:      // find the high bound of the range, O(lgn)
23:      start =low_bound, end =n;
24:      while(start < end)
25:      {
26:        int mid = (start + end)/2;
27:        if(A[mid] > target)
28:        {
29:          end = mid;
30:          continue;
31:        }
32:        start = mid+1;
33:      }
34:      int high_bound = start-1;
35:      result.clear();
36:      result.push_back(low_bound);
37:      result.push_back(high_bound);
38:      return result;
39:    }
``````

#### 1 comment:

Jarvis said...

the complexity is no longer O(lgn), right?