61. Search for a Range【medium】
61. Search for a Range【medium】
Given a sorted array of n integers, find the starting and ending position of a given target value.
If the target is not found in the array, return [-1, -1].
Example
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].
Challenge
O(log n) time.
解法一：
1 class Solution { 2 public: 3 /* 4 * @param A: an integer sorted array 5 * @param target: an integer to be inserted 6 * @return: a list of length 2, [index1, index2] 7 */ 8 vector<int> searchRange(vector<int> &A, int target) { 9 if (A.empty()) { 10 return vector<int>(2, -1); 11 } 12 13 vector<int> result; 14 15 //find first 16 int start = 0; 17 int end = A.size() - 1; 18 19 while (start + 1 < end) { 20 int mid = start + (end - start) / 2; 21 if (A[mid] == target) { 22 end = mid; 23 } 24 else if (A[mid] < target) { 25 start = mid; 26 } 27 else if (A[mid] > target) { 28 end = mid; 29 } 30 } 31 32 if (A[start] == target) { 33 result.push_back(start); 34 } 35 else if (A[end] == target) { 36 result.push_back(end); 37 } 38 else { 39 return vector<int>(2, -1); 40 } 41 42 //find last 43 start = 0; 44 end = A.size() - 1; 45 46 while (start + 1 < end) { 47 int mid = start + (end - start) / 2; 48 if (A[mid] == target) { 49 start = mid; 50 } 51 else if (A[mid] < target) { 52 start = mid; 53 } 54 else if (A[mid] > target) { 55 end = mid; 56 } 57 } 58 59 if (A[end] == target) { 60 result.push_back(end); 61 } 62 else if (A[start] == target) { 63 result.push_back(start); 64 } 65 66 return result; 67 } 68 };