problem:
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]
.
thinking:
(1)又是对二分搜索的变形,我的策略是当遇到 A[mid] = target时,以mid为中心往两边探测,搜索区间范围。
code:
class Solution { public: vector<int> searchRange(int A[], int n, int target) { if(n==0) { res.push_back(-1); res.push_back(-1); return res; } if(n==1) { if(A[0]==target) { res.push_back(0); res.push_back(0); return res; } else { res.push_back(-1); res.push_back(-1); return res; } }//if binary_search(A,0,n-1,target); return res; } protected: void binary_search(int A[], int left, int right, int target) { if(left>right) { res.push_back(-1); res.push_back(-1); return; } int mid = (left+right)/2; if(A[mid]==target) { int i=mid,j=mid; while(i>=left && i<=right && A[i]==target) i--; res.push_back(++i); while(j>=left && j<=right &&A[j]==target) j++; res.push_back(--j); return; } else if(A[mid]>target) binary_search(A,left,mid-1,target); else binary_search(A,mid+1,right,target); } private: vector<int> res; };
leetcode 题解 || Search for a Range 问题
原文:http://blog.csdn.net/hustyangju/article/details/44617583