forked from tanus786/CP-Codes-HackOctober-Fest-2023
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathFind_first_andLast_Position of an element in given array
66 lines (64 loc) · 1.43 KB
/
Find_first_andLast_Position of an element in given array
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
60
61
62
63
64
65
66
#include <iostream>
#include <vector>
using namespace std;
int firstOccurance(vector<int> arr, int target, int n)
{
int start = 0;
int end = n - 1;
int mid = start + (end - start) / 2;
int left = -1;
while (start <= end)
{
if (arr[mid] == target)
{
left = mid;
end = mid - 1;
}
else if (arr[mid] > target)
{
end = mid - 1;
}
else
{
start = mid + 1;
}
mid = start + (end - start) / 2;
}
return left;
}
int lastOccurance(vector<int> arr, int target, int n)
{
int start1 = 0;
int end1 = n - 1;
int mid1 = start1 + (end1 - start1) / 2;
int right = -1;
while (start1 <= end1)
{
if (arr[mid1] == target)
{
right = mid1;
start1 = mid1 + 1;
}
else if (arr[mid1] > target)
{
end1 = mid1 - 1;
}
else
{
start1 = mid1 + 1;
}
mid1 = start1 + (end1 - start1) / 2;
}
return right;
}
int main()
{
vector<int>arr{1, 2, 3, 4, 4, 5, 7};
int n = arr.size();
int target;
cout<<"Enter the element from the array to find the first and last position of the target element: ";
cin>>target;
cout<<"First Position:-" << firstOccurance(arr, target, n) << endl;
cout << "Last position:-"<<lastOccurance(arr, target, n) << endl;
return 0;
}