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 int findLeft(int A[], int n, int target)
02 {
03     int p=0;
04     int q=n1;
05     while(p<=q)
06     {
07         if(p==q)
08         {
09             if(A[p]==target)
10                 return p;
11             return 1;
12         }
13         int t=p+(qp)/2;
14         if(A[t]>target)
15             q=t1;
16         else if(A[t]<target)
17             p=t+1;
18         else
19             q=t;
20     }
21     return 1;
22 }
23 int findRight(int A[], int n, int target)
24 {
25     int p=0;
26     int q=n1;
27     while(p<=q)
28     {
29         if(p==q)
30         {
31             if(A[p]==target)
32                 return p;
33             return 1;
34         }
35         int t=q(qp)/2;
36         if(A[t]>target)
37             q=t1;
38         else if(A[t]<target)
39             p=t+1;
40         else
41             p=t;
42     }
43     return 1;
44 }
45 
46 class Solution {
47 public:
48     vector<int> searchRange(int A[], int n, int target) {
49         // Start typing your C/C++ solution below
50         // DO NOT write int main() function
51         vector<int> result;
52         int left=findLeft(A,n,target);
53         if(left==-1)
54         {
55             result.push_back(1);
56             result.push_back(1);
57             return result;
58         }
59         int right=findRight(A,n,target);
60         result.push_back(left);
61         result.push_back(right);
62         return result;
63     }
64 };
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