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].

C++:
01 vector<int> searchRange(int A[], int n, int target) {
02       vector<int> result(2);
03       result[0]=-1;
04       result[1]=-1;
05       int i=0;
06       int j=n1;
07       while(i<j){
08           int mid=(i+j)/2;
09           if(A[mid]<target)
10               i=mid+1;
11           else if(A[mid]>=target)
12               j=mid;
13       }
14       if(A[j]!=target)
15           return result;
16       else
17           result[0]=j;
18       i=0;
19       j=n1;
20       while(i<j){
21           int mid=j(ji)/2;
22           if(A[mid]<=target)
23               i=mid;
24           else
25               j=mid1;
26       }
27       result[1]=i;
28       return result;
29 }
Advertisements
This entry was posted in Array and linked list, Binary search. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s