/
FirstAndLastPositionInSortedArray.cpp
59 lines (44 loc) · 1.14 KB
/
FirstAndLastPositionInSortedArray.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
Problem statement
You have been given a sorted array/list 'arr' consisting of ‘n’ elements.
You are also given an integer ‘k’.
Now, your task is to find the first and last occurrence of ‘k’ in 'arr'.
Note :
1. If ‘k’ is not present in the array, then the first and the last occurrence will be -1.
2. 'arr' may contain duplicate elements.
//code
pair<int, int> firstAndLastPosition(vector<int>& arr, int n, int k)
{
int first = -1;
int last = -1;
int start = 0;
int end = n-1;
while(start <= end){
int mid = start + (end - start)/2;
if(arr[mid] == k){
first = mid;
end = mid-1;
}
else if(arr[mid] < k){
start = mid +1;
}
else{
end = mid -1;
}
}
start = 0;
end = n-1;
while(start <= end){
int mid = start + (end - start) / 2;
if(arr[mid] == k){
last = mid;
start = mid+1;
}
else if(arr[mid] < k){
start = mid +1;
}
else{
end = mid -1;
}
}
return make_pair(first,last);
}