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
|
// 34. Find First and Last Position of Element in Sorted Array
#include <stdio.h>
#include <stdlib.h>
/*
* given an array of integers 'nums' sorted in non-decreasing order, find the
* starting ending position of a given 'target' value. if target is not found in
* the array, return '[-1, -1]'. you must write an algorithm with O(log n)
* runtime complexity
*/
int *searchRange(int *nums, int nums_size, int target, int *return_size) {
int l = 0, r = nums_size - 1, mid = r / 2;
*return_size = 2;
int *ans = malloc(sizeof(int) * 2);
ans[0] = -1;
ans[1] = -1;
while (l <= r) {
mid = l + (r - l) / 2;
if (target == nums[mid]) {
int mid2 = mid;
while (l < mid) {
int l_mid = (mid + l) / 2;
if (nums[l_mid] < target)
l = l_mid + 1;
else
mid = l_mid;
}
while (mid2 < r) {
int r_mid = (mid2 + r + 1) / 2;
if (nums[r_mid] > target)
r = r_mid - 1;
else
mid2 = r_mid;
}
ans[0] = l;
ans[1] = r;
return ans;
} else if (target < nums[mid])
r = mid - 1;
else if (target > nums[mid])
l = mid + 1;
}
return ans;
}
int main() {
int n1[] = {5, 7, 7, 8, 8, 10}, n2[] = {5, 7, 7, 8, 8, 10}, n3[] = {};
int *sr1 = searchRange(n1, 6, 8, NULL);
int *sr2 = searchRange(n2, 6, 6, NULL);
int *sr3 = searchRange(n3, 0, 0, NULL);
for (int i = 0; i < 2; i++)
printf("%d ", sr1[i]); // expect: 3 4
printf("\n");
for (int i = 0; i < 2; i++)
printf("%d ", sr2[i]); // expect: -1 -1
printf("\n");
for (int i = 0; i < 2; i++)
printf("%d ", sr3[i]); // expect: -1 -1
printf("\n");
}
|